Wenn das Verfahren nach Beendigung die kürzesten Wege zu allen Knoten berechnet hat, dann muss sicherlich für alle Kanten (u,v) in E gelten, dass Dist(v) <= Dist(u) + c(u,v) ist, denn ansonsten wäre es kürzer über u und die Kante (u,v) nach v zu gehen. Die folgende Aussage zeigt, daß unser Verfahren zumindest diese notwendige Bedingung erfüllt:

Beweis:

Die Aussage gilt sicherlich in dem Moment, in dem u aufgenommen wird. Wenn sie zu einem späteren Zeitpunkt nicht mehr gilt, muss Dist(u) verringert worden sein. Da Dist(v) nicht wächst, kann dies wiederum nur passiert sein, als ein Knoten w in M aufgenommen und Dist(u) = d(w) + c(w,u) gesetzt wurde. Da aber nach der obigen Aussage d(w) >= d(u) und c(w,u) >= 0, folgt Dist(u) >= d(u), Widerspruch.

Aus der letzten Aussage ergibt sich nun umittelbar, daß der Dijkstra-Algorithmus korrekt arbeitet.

---