Editing Bellman–Ford algorithm

Jump to: navigation, search

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>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.
+
* 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.
  

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)