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 Knoten 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.