Content deleted Content added
Jellyworld (talk | contribs) |
Minor mistakes were fixed |
||
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)-1'' edges. (If a path contained more than ''V(G)-1'' edges, it must contain some vertex ''v'' twice. Then, it can be shortened by removing the part between the first occurrence of ''v'' and the second occurrence. This means that it was not the shortest path.)
==Implementations==
| |||