Bellman–Ford algorithm: Difference between revisions

Revision as of 03:12, 21 February 2024

Revision as of 05:52, 21 February 2024

Line 97:

<code>v.distance := u.distance + uv.weight</code>. By inductive assumption, <code>u.distance</code> is the length of some path from ''source'' to ''u''. Then <code>u.distance + uv.weight</code> is the length of the path from ''source'' to ''v'' that follows the path from ''source'' to ''u'' and then goes to ''v''.

For the second part, consider a shortest path ''P'' (there may be more than one) from ''source'' to ''v'' with at most ''i'' edges. Let ''u'' be the last vertex before ''v'' on this path. Then, the part of the path from ''source'' to ''vu'' is a shortest path from ''source'' to ''u'' with at most ''i-1'' edges, since if it were not, then there must be some strictly shorter path from ''source'' to ''u'' with at most ''i-1'' edges, and we could then append the edge ''uv'' to this path to obtain a path with at most ''i'' edges that is strictly shorter than ''P''—a contradiction. By inductive assumption, <code>u.distance</code> after ''i''−1 iterations is at most the length of this path from ''source'' to ''u''. Therefore, <code>uv.weight + u.distance</code> is at most the length of ''P''. In the ''i^th'' iteration, <code>v.distance</code> gets compared with <code>uv.weight + u.distance</code>, and is set equal to it if <code>uv.weight + u.distance</code> is smaller. Therefore, after ''i'' iterations, <code>v.distance</code> is at most the length of ''P'', i.e., the length of the shortest path from ''source'' to ''v'' that uses at most ''i'' edges.

If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices ''v''[0], ..., ''v''[''k''−1],