Dijkstra-Algorithmus             Das kürzeste-Wege-Problem             Gliederung Beweis zum Dijkstra-Algorithmus I 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. Allerding ist die "Kreisförmigkeit" relativ zu den gewählten Distanzen zu verstehen. Bezeichnen wir mit d(u) der Wert von Dist(u) zu dem Zeitpunkt, zu dem u in die Menge M aufgenommen wird. Dann gilt: Lemma 1   Wird u vor v in M aufgenommen, so gilt d(u) <= d(v). 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, muß 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. 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. weiter