Bellman–Ford algorithm: Difference between revisions

Revision as of 16:53, 4 April 2004

Revision as of 17:05, 10 April 2004

Line 36:

'''End of proof.'''

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 occuranceoccurrence of ''v'' and the second occuranceoccurrence. This means that it was not the shortest path.)

== Applications in routing ==