Bellman–Ford algorithm: Difference between revisions

Revision as of 04:36, 1 April 2004

Revision as of 16:33, 4 April 2004

Line 21:

== Proof of the Algorithm ==

{{msg:inuse}}

The correctness of the algorithm can be shown by [[mathematical induction|induction]]. The precise statement shown by induction is:

'''Lemma'''. After ''i'' steps, Distance(u) is equalat least the distance of the shortest path from ''s'' to ''u'' and at most the distance of the shortest path from ''s'' to ''u'' with at most ''i+1'' edges.

* infinity if there is no path from s to u with at most ''i+1'' edges;

* the length of the shortest path with at most ''i+1'' edges from s to u.

The correctness of the algorithm follows from the lemma together with the observation that shortest path between any two vertices must contain at most ''V(G)'' edges. (If a path contained more than ''V(G)'' edges, it must contain some vertex ''v'' twice. Then, it can be shortened by removing the part between the first occurance of ''v'' and the second occurance. This means that it was not the shortest path.)

== Applications in routing ==