1. Welt
  2. Quests
  3. #1499
Alexander Fufaev

Dijkstra-Algorithmus

aus dem Bereich: Quests

Deine Aufgabe ist...

Ungerichteter, gewichteter, zyklischer Graph mit 6 Kanten Speichern | Info
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.

Allgemeine 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ö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:

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.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.