Content deleted Content added
fixing proof of correctness |
finished correctness proof |
||
Line 21:
== 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'' repetitions of ''for'' cycle:
'''Lemma'''. After ''i'' steps, Distance(u) is at 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.▼
* If Distance(u) is not infinity, it is equal to the length of some path from ''s'' to ''u'';
▲
'''Proof'''. For the base case of induction, consider ''i=0'' and the moment before ''for'' cycle is executed for the first time. Then, for vertex ''s'', ''Distance(s)=0'' which is correct. For other vertices, ''Distance(u)=infinity'' which is also correct because there is no path from ''s'' to ''u'' with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when Distance is updated by ''Distance(v) = Distance(u) + w(u,v)'' step. By inductive assumption, ''Distance(u)'' is the length of some path from ''s'' to ''u''. Then, ''Distance(u) + w(u,v)'' is the length of the path from ''s'' to ''v'' that first goes from ''s'' to ''u'' and then from ''u'' to ''v''.
For the second part, consider the shortest path from ''s'' to ''u'' with at most ''i'' edges. Let ''v'' be the last vertex before ''u'' on this path. Then, the part of the path from ''s'' to ''v'' is the shortest path between ''s'' to ''v'' with ''i-1'' edges. By inductive assumption, ''Distance(v)'' after ''i-1'' cycles is at most the length of this path. Therefore, ''Distance(v)+w(u,v)'' is at most the length of the path from ''s'' to ''u''. In the ''i<sup>th</sup>'' cycle, ''Distance(u)'' gets compared with ''Distance(v)+w(u,v)'' and set equal to it, if ''Distance(v)+w(u,v)'' was smaller. Therefore, after ''i'' cycles ''Distance(u)'' is at most the length of the path from ''s'' to ''u''.
'''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 occurance of ''v'' and the second occurance. This means that it was not the shortest path.)
| |||