Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #342

Aufgabe mit Lösung Dijkstra-Algorithmus

Ungerichteter, gewichteter, zyklischer Graph mit 6 Kanten.

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:

IterationABCDEFVerwaltung
0Distanz:
Vorgänger:
-
-
-
-
-
-
-
-
-
-
-
-
Vorrat: -
Erledigt: -
Aktuell: -
Nachfolger: -

Lösung

Lösung anzeigen

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:

IterationABCDEFVerwaltung
0Distanz:
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:

IterationABCDEFVerwaltung
0Distanz:
Vorgänger:
0
-

-

-

-

-

-
Vorrat: A
Erledigt: -
Aktuell: -
Nachfolger: -
1Distanz:
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:

IterationABCDEFVerwaltung
0Distanz:
Vorgänger:
0
-

-

-

-

-

-
Vorrat: A
Erledigt: -
Aktuell: -
Nachfolger: -
1Distanz:
Vorgänger:
0
-
1
A
4
A

-
9
A

-
Vorrat: A
Erledigt: -
Aktuell: A
Nachfolger: E,B,C
2Distanz:
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.

IterationABCDEFVerwaltung
0Distanz:
Vorgänger:
0
-

-

-

-

-

-
Vorrat: A
Erledigt: -
Aktuell: -
Nachfolger: -
1Distanz:
Vorgänger:
0
-
1
A
4
A

-
9
A

-
Vorrat: A
Erledigt: -
Aktuell: A
Nachfolger: E,B,C
2Distanz:
Vorgänger:
0
-
1
A
4
A

-
8
B
7
B
Vorrat: E,B,C
Erledigt: A
Aktuell: B
Nachfolger: E,F
3Distanz:
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
4Distanz:
Vorgänger:
0
-
1
A
4
A
6
C
8
B
7
B
Vorrat: D,E,F
Erledigt: A,B,C
Aktuell: D
Nachfolger: -
5Distanz:
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
6Distanz:
Vorgänger:
0
-
1
A
4
A
6
C
8
B
7
B
Vorrat: E
Erledigt: A,B,C,D,F
Aktuell: E
Nachfolger: -
7Distanz:
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.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?