Content deleted Content added
+comments to program |
added proof sketch |
||
Line 22:
== Proof of the Algorithm ==
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 equal to
* 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 ==
| |||