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

Die Ameisen starten gleichzeitig beim Startknoten. In alle Richtungen schwärmen sie gleich schnell aus:

Erreichen Ameisen einen ersten Nachbarknoten, so teilen sie sich sogleich und folgen allen weiteren Verzweigungen, immer noch im genau gleichen Tempo.

Dasselbe passiert nun bei verschiednen Knoten. Teilweise marschieren Ameisen auf der selben Kante aufeinander zu.

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.

So geht das Entdecken weiter: Bei neuen Knoten teilen sich die Ameisen, bei Kanten begegnen sie sich.

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

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!

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!

Warnung

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.

Aufgabe

Führe den Dijkstra-Algorithmus durch: Finde den kürzesten Weg in umgekehrter Richtung, also vom Knoten L zum Knoten I.

• Zeichne dein Fortschritt analog zum Beispiel im Graphen auf
• Führe daneben eine Open- und eine Closed-List

gerichtete Graphen

Das Ganze funktioniert auch für sogenannt «gerichtete Graphen», also z.B. Karten mit Einbahnstrassen:

Aufgabe

Führe den Dijkstra-Algorithmus aus: erstelle eine Entfernungstabelle für das Hotel Adler. Finde die kürzesten Wege vom Knoten A zu allen anderen Knoten.

• Zeichne dein Fortschritt analog zum Beispiel im Graphen auf
• Führe daneben eine Open- und eine Closed-List