Folgerungen             Das kürzeste-Wege-Problem             Gliederung



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. Dist(s) := 0, U leer
    2. for v aus V mit (s,v) aus E do
    3.     Dist(v) = c(s,v), Vor(v) = s
    4.     U = U + {v}
    5. end for
    6. while U nicht leer do
    7.     wähle u aus U mit Dist(u) minimal                               (finde min)
    8.     U = U - {u}                                                           (lösche min)
    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