Schaut man sich den Ablauf des Verfahrens an, so bekommt man den Eindruck, daß sich die Menge M "kreisförmig" um den Startknoten s ausbreitet. Allerdings ist die "Kreisförmigkeit" relativ zu den gewählten Distanzen zu verstehen.

Bezeichnen wir mit d(u) den Wert von Dist(u) zu dem Zeitpunkt, zu dem u in die Menge M aufgenommen wird. Dann gilt:

Beweis:

Angenommen es existieren Knoten u und v, so daß u vor v aufgenommen wird, aber d(u) > d(v) gilt. Unter allen diesen Knoten v wähle den als ersten in M aufgenommenen. In dem Moment, in dem u aufgenommen wird, gilt d(u) = Dist(u) <= Dist(v). Da per Definition d(u) nicht mehr verändert wird, muss später Dist(v) verringert worden sein. Dies kann nur passieren, wenn ein Knoten w in die Menge M aufgenommen und Dist(v) = Dist(w) + c(w,v) gesetzt wird. Sei w der letzte solche Knoten, d.h. es gilt d(v) = d(w) + c(w,v). Nach Wahl von v gilt aber d(u) <= d(w). Da c(w,v) >= 0, folgt d(v) >= d(u), Widerspruch.

---