Aufgabe mit Lösung Dijkstra-Algorithmus
Ermittle alle kürzesten Wege vom Startknoten A zu allen anderen Knoten des Graphen. Benutze dafür den Dijkstra-Algorithmus und gib nach jedem bearbeiteten Knoten die aktuelle Distanz und den Vorganger für jeden Knoten an.
Lösungstipps
Erstelle eine Tabelle der folgenden Form:
| Iteration | A | B | C | D | E | F | Verwaltung | |
|---|---|---|---|---|---|---|---|---|
| 0 | Distanz: Vorgänger: | - - | - - | - - | - - | - - | - - | Vorrat: - Erledigt: - Aktuell: - Nachfolger: - |
Lösungen
Lösung
Der Dijkstra-Algorithmus wird hier mit dem Knoten A gestartet. Die Distanz von A zu A ist 0. Und A hat keinen Vorgänger. Alle anderen Knoten wurden noch nicht besucht und werden deshalb mit Distanz = ∞ initialisiert:
| Iteration | A | B | C | D | E | F | Verwaltung | |
|---|---|---|---|---|---|---|---|---|
| 0 | Distanz: Vorgänger: | 0 - | ∞ - | ∞ - | ∞ - | ∞ - | ∞ - | Vorrat: A Erledigt: - Aktuell: - Nachfolger: - |
Bei der nächsten Iteration werden die Nachfolger-Knoten von A betrachtet. Die Nachfolger sind E, B und C. Der Vorgänger von E, B und C ist A und die Distanz von A zu E, B und C wird an der Graph-Skizze abgelesen:
| Iteration | A | B | C | D | E | F | Verwaltung | |
|---|---|---|---|---|---|---|---|---|
| 0 | Distanz: Vorgänger: | 0 - | ∞ - | ∞ - | ∞ - | ∞ - | ∞ - | Vorrat: A Erledigt: - Aktuell: - Nachfolger: - |
| 1 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | ∞ - | 9 A | ∞ - | Vorrat: A Erledigt: - Aktuell: A Nachfolger: E,B,C |
Damit wurde der Knoten A besucht und die Distanz zu seinen Nachbarknoten eingetragen. A ist erledigt. Die Nachfolgerknoten von A wandern in den Vorrat (siehe Spalte "Verwaltun"). Nun wird der günstigste Weg im Vorrat in der Tabelle abgelesen. Der günstigste Weg geht zu B:
| Iteration | A | B | C | D | E | F | Verwaltung | |
|---|---|---|---|---|---|---|---|---|
| 0 | Distanz: Vorgänger: | 0 - | ∞ - | ∞ - | ∞ - | ∞ - | ∞ - | Vorrat: A Erledigt: - Aktuell: - Nachfolger: - |
| 1 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | ∞ - | 9 A | ∞ - | Vorrat: A Erledigt: - Aktuell: A Nachfolger: E,B,C |
| 2 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | ∞ - | 8 B | 7 B | Vorrat: E,B,C Erledigt: A Aktuell: B Nachfolger: E,F |
Beachte, dass der Weg zu E aktualisiert wurde, denn es wurde ein kürzerer Weg gefunden, nämlich, wenn E über B besucht wird. Analog wird bei der dritten Iteration vorgegangen. Die Nachfolger wanden in den Vorrat (wobei gleiche Knoten nicht doppelt aufgezählt werden). Und die bereits erledigten Knoten werden nicht mehr betrachtet.
| Iteration | A | B | C | D | E | F | Verwaltung | |
|---|---|---|---|---|---|---|---|---|
| 0 | Distanz: Vorgänger: | 0 - | ∞ - | ∞ - | ∞ - | ∞ - | ∞ - | Vorrat: A Erledigt: - Aktuell: - Nachfolger: - |
| 1 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | ∞ - | 9 A | ∞ - | Vorrat: A Erledigt: - Aktuell: A Nachfolger: E,B,C |
| 2 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | ∞ - | 8 B | 7 B | Vorrat: E,B,C Erledigt: A Aktuell: B Nachfolger: E,F |
| 3 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | 6 C | 8 B | 7 B | Vorrat: C,E,F Erledigt: A,B Aktuell: C Nachfolger: D,F |
| 4 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | 6 C | 8 B | 7 B | Vorrat: D,E,F Erledigt: A,B,C Aktuell: D Nachfolger: - |
| 5 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | 6 C | 8 B | 7 B | Vorrat: E,F Erledigt: A,B,C,D Aktuell: F Nachfolger: E |
| 6 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | 6 C | 8 B | 7 B | Vorrat: E Erledigt: A,B,C,D,F Aktuell: E Nachfolger: - |
| 7 | Distanz: Vorgänger: | 0 - | 1 A | 4 A | 6 C | 8 B | 7 B | Vorrat: - Erledigt: A,B,C,D,F,E Aktuell: - Nachfolger: - |
Alle Knoten wurden besucht. Der Dijkstra-Algorithmus endet hier. Nun können in der letzten Zeile alle kürzesten Wege von A zu einem beliebigen anderen Knoten abgelesen werden. Der kürzeste Weg von A nach E ist: ABE. Um diesen zu bestimmen, wird der Vorgänger von E abgelesen. Der Vorgänger ist B. Dann wird der Vorgänger von B abgelesen. Das ist A.