Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
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.