Mit der Breitensuche haben wir einen Weg gefunden, aber nicht zwingenderweise den schnellsten. Wie können wir nun aber die Gewichte der Kanten berücksichtigen und den schnellsten Weg finden? Dafür führt Jens Gallenbacher die Idee mit den Ameisen ein:
Ameisen
- Start
- Verzweigung
- Aufeinander Zu
- Kollision
- weiter...
- Gefunden
Start
Die Ameisen starten gleichzeitig beim Startknoten. In alle Richtungen schwärmen sie gleich schnell aus:
Verzweigung
Erreichen Ameisen einen ersten Nachbarknoten, so teilen sie sich sogleich und folgen allen weiteren Verzweigungen, immer noch im genau gleichen Tempo.
Aufeinander Zu
Dasselbe passiert nun bei verschiednen Knoten. Teilweise marschieren Ameisen auf der selben Kante aufeinander zu.
Kollision
Treffen sich aus unterschiedlicher Richtung kommende Ameisen auf einer Kante, so wird diese Kante entfernt: Man weiss dass die beiden Knoten, von wo die Ameisen aus auf diese Kante gekommen sind, bereits entdeckt sind.
weiter...
So geht das Entdecken weiter: Bei neuen Knoten teilen sich die Ameisen, bei Kanten begegnen sie sich.
Gefunden
Schlussendlich ist jeder Knoten von Ameisen entdeckt worden. Und zwar immer auf dem schnellsten Weg vom Startknoten aus. Wenn wir die nicht-durchgestrichenen Kanten zurück zum Start verfolgen, haben wir also den schnellsten Weg gefunden.
Dijkstra
Wir wollen versuchen den «Ameisen»-Algorithmus für den Computer umzusetzen. Es macht nämlich wenig Sinn, sich gleichmässig auf den Kanten fortzubewegen. Wir kennen ja die Distanzen zwischen den Knoten. Statt zu schauen, welche Ameisen zuerst beim nächsten Knoten sind, wählen wir den «besten» Knoten von unserer Open-List und gehen dort weiter! Dazu notieren wir auf unser Open-List immer die bereits zurückgelegte Distanz vom Startknoten.
Vorbereitung
Der Startknoten kommt auf die Open-List. Die zurückgelegte Distanz (von Startknoten zu Startknoten) ist natürlich 0.
Closed-List: –
Open-List: I (0)
- Schritt 1
- Vorbereitung Schritt 2
- Schritt 2
- Schritt 3
Schritt 1
Wir fügen alle Nachbarn des Startknotens auf die Open-List. Dabei berechnen wir wie weit es vom Startknoten zum jeweiligen Knoten ist.
I kommt auf die Closed-List.
Closed-List: I
Open-List: M (43), C (40), B (34), H (65), P (55)
Vorbereitung Schritt 2
Wir suchen den besten Kandidaten aus unserer Open-List heraus. Der Knoten B hat die kleinste Distanz, also machen wir dort weiter!
Closed-List: I
Open-List: M (43), C (40), B (34), H (65), P (55)
Schritt 2
Wir berechnen für alle Nachbarn des Knotens B ihre Distanz vom Startknoten über B. Ist der Knoten noch nicht auf der Open-List, wird dieser hinzugefügt. Ist ein Knoten – wie hier der Knoten H – bereits auf der Open-List, schauen wir, ob wir einen kürzeren Weg gefunden haben. Wenn ja, aktualisieren wir den Knoten auf der Open-List.
B kommt auf die Closed-List.
Closed-List: I, B
Open-List: M (43), C (40), H (64), P (55), X (60), A (103), D (98), Z (66)
Schritt 3
Der nächste «beste» Kandidat auf unserer Open-List ist C. Die Nachbarn von C sind aber bereits auf der Open-List – und zwar mit kürzerer Distanz als über C.
C kommt auf die Closed-List.
Closed-List: I, B, C
Open-List: M (43), H (64), P (55), X (60), A (103), D (98), Z (66)
Der Algorithmus
Der Algorithmus kann wie folgt schematisch dargestellt werden:
Endzustand
Wenn wir nur den besten Weg finden wollen, können wir den Algorithmus abbrechen, sobald der Zielknoten der «beste» Kandidat auf der Open-List ist. Dann wissen wir: Es gibt keinen kürzeren Weg!
Wenn der Zielknoten nur auf der Open-List ist, könnte es immer noch einen besseren Weg geben! Wir haben ja erst einen Weg gefunden, ev. gibt es über einen anderen Knoten auf der Open-List einen schnelleren. Wenn aber der Zielknoten der «beste» Kandidat ist, dann kann es keinen schnelleren Weg mehr geben!
Wir können den Algorithmus auch weiterlaufen lassen. Am Schluss erhalten wir dann einen «Baum» (alle roten Kanten). Dieser Baum stellt die schnellsten Wege von I zu jedem anderen Knoten des Graphen dar.
Führen Sie den Dijkstra-Algorithmus durch: Finden Sie den kürzesten Weg in umgekehrter Richtung, also vom Knoten L zum Knoten I.
-
Zeichnen Sie ihren Fortschritt analog zum Beispiel im Graphen auf
-
Führen Sie daneben eine Open- und eine Closed-List
gerichtete Graphen
Das Ganze funktioniert auch für sogenannt «gerichtete Graphen», also z.B. Karten mit Einbahnstrassen:
- Schilda
- Knoten
- Gerichteter Graph
Führen Sie den Dijkstra-Algorithmus aus: erstellen Sie eine Entfernungstabelle für das Hotel Adler. Finden Sie die kürzesten Wege vom Knoten A zu allen anderen Knoten.
-
Zeichnen Sie ihr Fortschritt analog zum Beispiel im Graphen auf
-
Führen Sie daneben eine Open- und eine Closed-List
Dijkstra