Beweis:

Wir zeigen per Induktion, daß die notwendige Bedingung auch hinreichend ist. Sei dazu v ein Knoten und u ein Vorgänger von v auf einem kürzesten Weg. Per Induktion können wir annehmen, daß Dist(u) die Länge eines kürzesten Weges nach u ist. Da Dist(v) <= Dist(u) + c(u,v) , ist dann Dist(v) die Länge eines kürzesten Weges nach v.

Der Beweis zeigt, daß sich die Werte Dist(u) nicht mehr ändern, nach dem u in M aufgenommen worden ist. Wir können daher folgende Vereinfachungen vornehmen:

---