# Editing Bellman–Ford algorithm

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 22: | Line 22: | ||

We proceed by induction: | We proceed by induction: | ||

* When <math>N=0</math>, there is at least 1 correct entry in <i>dist</i>, the one stating that the distance from the source to itself is zero. | * When <math>N=0</math>, there is at least 1 correct entry in <i>dist</i>, the one stating that the distance from the source to itself is zero. | ||

− | * Now suppose that <math>N</math> passes have occurred and that we know the shortest-path distances from the source to <math>N+1</math> of the vertices. Now, either <math>N</math> is equal to <math>V-1</math>, and we are done, or the vertices may be partitioned into two sets: <math>S</math>, which contains <math>N+1</math> vertices for which we already know shortest-path distances (with any <math> | + | * Now suppose that <math>N</math> passes have occurred and that we know the shortest-path distances from the source to <math>N+1</math> of the vertices. Now, either <math>N</math> is equal to <math>V-1</math>, and we are done, or the vertices may be partitioned into two sets: <math>S</math>, which contains <math>N+1</math> vertices for which we already know shortest-path distances (with any <math>n+1</math> being chosen if there are more than this number), and <math>\overline{S}</math>, which contains the rest. Now, since a shortest-paths tree exists (it always does when there are no negative-weight cycles; the proof is in the [[Shortest path]] article), there must exist some vertex <i>w</i> in <math>\overline{S}</math> whose parent <i>u</i> in the shortest-paths tree is in <math>S</math>. Then, when the edge <i>(u,w)</i> is relaxed, the <i>dist</i> array will contain the correct shortest-path distance to <i>w</i>. Thus, after the next pass of the outer loop has occurred, <math>N+1</math> passes will have occurred in total, and the shortest-path distances to at least <math>(N+1)+1</math> vertices will be correctly known. |

Thus, when a negative-weight cycle does not exist, after the main loop has finished, all distances in <i>dist</i> are correct. Now, if an edge <i>(u,w)</i> still exists such that <code>dist[w] > dist[u]+wt(u,w)</code>, then the distances could not possibly have been correct, because relaxation of <i>(u,w)</i> would give a shorter path to <i>w</i>. Since this is a contradiction, the assumption of the non-existence of negative-weight cycles must be incorrect in this case. We see then that as long as there are no negative-weight cycles, the algorithm always computes all distances correctly and terminates successfully. | Thus, when a negative-weight cycle does not exist, after the main loop has finished, all distances in <i>dist</i> are correct. Now, if an edge <i>(u,w)</i> still exists such that <code>dist[w] > dist[u]+wt(u,w)</code>, then the distances could not possibly have been correct, because relaxation of <i>(u,w)</i> would give a shorter path to <i>w</i>. Since this is a contradiction, the assumption of the non-existence of negative-weight cycles must be incorrect in this case. We see then that as long as there are no negative-weight cycles, the algorithm always computes all distances correctly and terminates successfully. | ||