Dijkstra

nach Jens Gallenbacher: Abenteuer Informatik

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!

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.
Ⓘ 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 Ⓑ hat die kleinste Distanz, also machen wir dort weiter!

Schritt 2

Wir berechnen für alle Nachbarn des Knotens Ⓑ ihre Distanz über vom Startknoten über Ⓑ. Ist der Knoten noch nicht auf der Open-List, wird dieser hinzugefügt. Ist ein Knoten – wie hier der Knoten Ⓗ – 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.
Ⓑ 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 Ⓒ. Die Nachbarn von Ⓒ sind aber bereits auf der Open-List – und zwar mit kürzerer Distanz als über Ⓒ.
Ⓒ 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

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! (Achtung: Wenn der Zielknoten nur auf der Open-List ist, könnte es immer noch einen besseren Weg 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 Ⓘ zu jedem anderen Knoten des Graphen dar.

Führe den Dijkstra-Algorithmus aus: Finde den kürzesten Weg in umgekehrter Richtung, also vom Knoten Ⓛ zum Knoten Ⓘ.

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

Schilda

Das Ganze funktioniert auch für sogenannt «gerichtete Graphen»:

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

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