Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Dijkstra in Pseudocode

Knoten, die in die Menge M aufgenommen worden sind, heißen markiert. Für die Implementation des Dijkstra-Algorithmus ist es besser, an Stelle der Menge M die Menge 

U = {v aus V : Dist(v) < unendlich, v nicht aus M}

zu betrachten. Diese Menge, die aus den noch nicht markierten Knoten besteht, zu denen der Algorithmus schon einen provisorischen Weg gefunden hat, heißt Front. Neu formuliert heißt der Algorithmus jetzt so: 

    1. for all v aus V do
    2.     Dist(v) := unendlich, Vor(v) := leer
    3. end for
    4. Dist(s) := 0, Vor(s) := s, U := {s}
    5. while U nicht leer do
    6.     wähle u aus U mit Dist(u) minimal                               (finde Min)
    7.     U := U - {u}                                                              (lösche Min)
    8.     if u = t then STOP   # optional
    9.     for all (u,v) aus E do
    10.          if Dist(u) + c(u,v) < Dist(v) then
    11.               Dist(v) = Dist(u) + c(u,v), Vor(v) := u               (verringere)
    12.               if v nicht aus U then U := U + {v}                       (füge ein)
    13.          end if
    14.     end for
    15. end while


Wir wollen uns im folgenden eine Animation des Verfahrens anschauen: