Dijkstra-Algorithmus

Ein Navi findet in wenigen Sekunden die kürzeste Verbindung zwischen zwei Punkten. Wie macht es das?

Im Navi sind alle erreichbaren Orte als Knoten und die Wege zwischen ihnen als Kanten dargestellt. Die Kanten sind jeweils mit der Weglänge gewichtet. Schauen wir uns das Beispiel auf der rechten Seite an. Gesucht ist der kürzeste Pfad zwischen A und F.
Die Lösungsidee besteht darin, von A ausgehend den Graphen so zu traversieren ("durchschreiten"), dass als nächstes immer der Knoten besucht wird, der von A die bisher kürzeste Entfernung hat. Wir legen uns dazu eine Tabelle an, in der wir zu jedem Knoten die Länge des bisher kürzesten bekannten Pfades nach A notieren: Bei A tragen wir zu Beginn gleich 0 ein, bei allen anderen Knoten den Wert ∞ (unendlich), da wir noch nicht wissen, wie lange der jeweils kürzeste Pfad zu A ist.

1. Schritt:

Unter den noch nicht besuchten Knoten (bisher wurde noch keiner besucht), wählen wir denjenigen mit dem kürzesten bisher bekannten Pfad zu A aus. Es ist in diesem Fall der Knoten A selbst. Wir markieren ihn grün (grün heißt "besucht").
Wir betrachten (nicht "besuchen"!) jetzt alle von A aus erreichbaren Knoten, die noch nicht besucht wurden (also C und E) und sehen nach, ob der Pfad zu ihnen über den gerade besuchten Knoten kürzer ist als der kürzeste derzeit bekannte:
- Der Pfad von A über A zu C ist kürzer als der bisher bekannte (3 < ∞), daher tragen wir bei C die Pfadlänge 3 ein. Zusätzlich notieren wir in blauer Farbe den Vorgängerknoten des bisher kürzesten Pfades zu C, nämlich A.
- Der Pfad von A über A zu E ist kürzer als der bisher bekannte (10 < ∞), daher tragen wir bei E die Pfadlänge 10 ein. Zusätzlich notieren wir in blauer Farbe den Vorgängerknoten des bisher kürzesten Pfades zu E, nämlich A.

2. Schritt:

Unter den noch nicht besuchten Knoten wählen wir denjenigen mit dem kürzesten bisher bekannten Pfad zu A aus. Es ist in diesem Fall der Knoten C. Wir markieren ihn grün.
Wir betrachten jetzt alle von C aus erreichbaren Knoten, die noch nicht besucht wurden (also B, D und E) und sehen nach, ob der Pfad von A über C zu ihnen kürzer ist als der kürzeste bisher bekannte:
- Der Pfad von A über C zu B hat die Länger 3 + 3 = 6 und ist damit kürzer als der bisher bekannte (6 < ∞), daher tragen wir bei B die Pfadlänge 6 und den Vorgängerknoten C ein.
- Der Pfad von A über C zu D hat die Länge 3 + 8 = 11 und ist damit kürzer als der bisher bekannte (11 < ∞), daher tragen wir bei D die Pfadlänge 11 und den Vorgängerknoten C ein.
- Der Pfad von A über C zu E hat die Länge 3 + 5 = 8 und ist damit kürzer als der bisher bekannte (8 < 10), daher tragen wir bei E die Pfadlänge 8 und den Vorgängerknoten C ein.

Wir wissen jetzt, dass der kürzeste Pfad von A zu C die direkte Verbindung zwischen den beiden Knoten ist und die Länge 3 hat.

Begründung:
Falls es einen kürzeren Pfad von A zu C gäbe, müsste dieser über einen Vorgängerknoten X führen, der weniger als 3 km von A entfernt ist. Dieser wäre aber dann bereits in einem der vorhergehenden Schritte besucht worden und bei diesem Besuch wäre die kürzere Pfadlänge A → … → X → C bei C notiert worden.

3. Schritt:

Unter den noch nicht besuchten Knoten ist B der mit dem kürzesten Pfad zu A. Wir markieren ihn grün.
Wir betrachten alle von B aus erreichbaren Knoten, die noch nicht besucht wurden (es ist nur D).
- Der Pfad von A über B nach D hat die Länge 11 und ist damit gleich lang wie der bisher kürzeste gefundene (über C). Es ist daher nichts weiter zu tun.

Wir wissen jetzt, dass der kürzeste Pfad von A zu B der Pfad A→C→B ist und die Länge 6 hat.

Begründung:
Falls es einen kürzeren Pfad von A zu B gäbe, müsste dieser über einen Vorgängerknoten X führen, der weniger als 6 km von A entfernt ist. Dieser wäre aber dann bereits in einem der vorhergehenden Schritte besucht worden und bei diesem Besuch wäre dann die kürzere Pfadlänge A→ … → X → B bei B notiert worden.

4. Schritt:

Unter den noch nicht besuchten Knoten ist E der mit dem kürzesten Pfad zu A. Wir markieren ihn grün.
Wir betrachten alle von E aus erreichbaren Knoten, die noch nicht besucht wurden (D und F).
- Der Pfad von A über E nach D hat die Länge 11 und ist kürzer als der bisher kürzeste gefundene (11 < 12). ⇒ Tragen wir ein!
- Der Pfad von A über E nach F hat die Länge 15 und ist kürzer als der bisher kürzeste gefundene (15 < ∞). Wir tragen bei F daher die Entfernung 15 und den Vorgänger E ein.

Wir haben einen Weg von A zu F gefunden. Sind wir jetzt fertig? Überlegen Sie genau!
Warum können wir ab jetzt sicher sein, dass der kürzeste Weg von A nach E derjenige über C mit Länge 8 ist? Formulieren Sie eine genaue Begründung unter Zuhilfenahme der zwei vorhergehenden gelben Kästen!

5. Schritt:

Unter den noch nicht besuchten Knoten ist D der mit dem kürzesten Pfad zu A. Wir markieren ihn grün.
Wir betrachten alle von D aus erreichbaren Knoten, die noch nicht besucht wurden (das ist nur noch F).
- Der Pfad von A über D nach F hat die Länge 14 und ist kürzer als der bisher kürzeste gefundene (14 < 15). Wer hätte das gedacht? ⇒ Tragen wir ein!

6. Schritt

Unter den noch nicht besuchten Knoten ist F derjenige mit dem kürzesten Pfad zu A. Wir markieren ihn grün.
Hoppla, das ist ja der Zielknoten. ⇒ Wir sind fertig!

Unsere Aufgabe bestand darin, den kürzesten Weg von A zu F zu finden:

a) Wir hatten am Ende alle Knoten besucht. Muss man immer alle Knoten eines Graphen besuchen, um den kürzesten Pfad von einem gegebenen Knoten zu einem anderen gegebenen Knoten zu finden? Falls "Nein": erweitern Sie den gegebenen Graphen um weiter Knoten und Pfade, so dass diese Knoten auf der Suche nach dem kürzesten Pfad von A nach F nicht besucht worden wären.
b) Wir wissen jetzt, dass der kürzeste Pfad von A nach F die Länge 14 hat. Aber wie verläuft nun dieser Pfad? Ermitteln Sie den Pfadverlauf unter Verwendung der blau notierten Vorgängerknoten!