Korollar 1

1. In der Schleife 4. genügt es, nur Knoten v zu betrachten, die nicht in M liegen.
2. Ist man nur an dem kürzesten Weg von s zu einem Zielknoten t interessiert, so genügt es, den Algorithmus zu stoppen, sobald t in M aufgenommen wird.

Damit können wir den Algorithmus etwas vereinfachen:

1. Setze Dist(s) :=  0, Vor(s) := s,   M :=  {s}
   Falls s = t, dann STOP   # optional
   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}
   Falls u = t, dann STOP   # optional
4. Für alle v aus V mit v nicht in M und (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.

Für die spätere Analyse der Laufzeit des Verfahrens in Abhängigkeit von der Größe des Graphen (Anzahl der Knoten und Anzahl der Kanten) formulieren wir im folgenden den Dijkstra-Algorithmus in einer Pseudoprogrammiersprache, wobei wir bereits auf die Operationen (z.B. finde Min) abheben, die die noch zu bestimmenden Datenstrukturen unterstützen müssen.

---