Einige Begriffe der Graphentheorie             Das kürzeste-Wege-Problem             Gliederung



Dijkstra-Algorithmus

Die Idee des Verfahrens besteht darin, schrittweise eine Menge M von Knoten zu vergrößern, für deren Elemente v wir bereits einen kürzesten Weg von s nach v gefunden haben. Allen anderen Knoten v , die nicht in M liegen, ordnen wir die Länge des bisher gefundenen kürzesten Weges zu.

Wir bezeichnen dazu mit   Dist(v)   die Länge des (bisher gefundenen) kürzesten Weges und mit   Vor(v)   den Vorgänger auf einem solchen Weg.

    1. Setze Dist(s) :=  0,  M :=  {s}
      Für v aus V mit   (s, v) aus E  setze   Dist(v)  :=  c(s, v)  und   Vor(v)  :=  s
      Für v aus V mit (s, v) nicht aus E setze Dist(v) = unendlich und Vor(v) = leer
    2. Bestimme u nicht aus M mit Dist(u) = min {Dist(v):v nicht aus M}
    3. Falls   Dist(u) = unendlich  , dann STOP. Andernfalls setze M = M vereinigt {u}
    4. Für alle v aus V mit (u, v) aus E:
      Falls   Dist(v)>Dist(u)+c(u,v)  , dann setze:
      Dist(v) = Dist(u)+c(u,v)
      Vor(v) = u
      5. Falls M ungleich V , dann gehe zu 2, sonst STOP.



Wir wollen uns im folgenden eine Animation des Verfahrens anschauen.

Ablauf des Dijkstra-Verfahrens