Bellman–Ford algorithm - Revision history

162.158.62.18 at 09:05, 25 June 2022

2022-06-25T09:05:06Z

162.158.62.94: removed unneeded html tag

2022-06-25T09:02:24Z

removed unneeded html tag

162.158.146.132: /* Intuitive explanation */

2017-11-03T00:35:15Z

‎Intuitive explanation

162.158.146.132: /* The algorithm */

2017-11-03T00:34:56Z

‎The algorithm

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:49:41Z

‎Proof of correctness for graphs containing no negative-weight cycles

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:46:37Z

‎Proof of correctness for graphs containing no negative-weight cycles

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:46:26Z

‎Proof of correctness for graphs containing no negative-weight cycles

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:46:13Z

‎Proof of correctness for graphs containing no negative-weight cycles

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:46:00Z

‎Proof of correctness for graphs containing no negative-weight cycles

141.52.249.2: /* Proof of correctness for graphs containing no negative-weight cycles */

2016-10-04T17:45:34Z

‎Proof of correctness for graphs containing no negative-weight cycles

@@ Line 1: / Line 1: @@
 The '''Bellman-Ford algorithm''' finds [[Shortest_path#Single-source_shortest_paths|single-source shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) When single-source shortest paths are all that which is needed, and not [[Shortest path#All-pairs_shortest_paths|all-pairs shortest paths]], The Bellman–Ford algorithm, with time complexity <math>\mathcal{O}(VE)</math>, outperforms the [[Floyd–Warshall algorithm]] at <math>\mathcal{O}(V^3)</math> in sparse graphs. It may also be combined with Dijkstra's algorithm to yield [[Johnson's algorithm]], which again outperforms Floyd–Warshall in sparse graphs.
+<pre>
 input G,v
 for each u ∈ V(G)
@@ Line 12: / Line 12: @@
       if dist[w] > dist[u]+wt(u,w)
            error "Graph contains negative-weight cycles"
 <i>G</i> is the directed, weighted graph in question, and <i>v</i> the source. The output is the array <i>dist</i>; at the completion of the algorithm, <i>dist[x]</i> contains the shortest-path distance from <i>v</i> to <i>x</i>. If the graph contains a cycle of negative weight, an error message is generated to that effect.

@@ Line 12: / Line 12: @@
       if dist[w] > dist[u]+wt(u,w)
            error "Graph contains negative-weight cycles"
-</pre>
 <i>G</i> is the directed, weighted graph in question, and <i>v</i> the source. The output is the array <i>dist</i>; at the completion of the algorithm, <i>dist[x]</i> contains the shortest-path distance from <i>v</i> to <i>x</i>. If the graph contains a cycle of negative weight, an error message is generated to that effect.

@@ Line 16: / Line 16: @@
 ==Theory of the algorithm==
-===Intuitive explanation===
 The algorithm works by performing a series of <i>relaxations</i>. A relaxation occurs whenever the current shortest distance from node <i>v</i> to node <i>w</i> is improved because, by travelling from <i>v</i> to some intermediate vertex <i>u</i>, and then from <i>u</i> to <i>w</i>, a shorter path is obtained. (Floyd–Warshall and Dijkstra's algorithms rely upon this same technique.) The key is that, after <i>n</i> passes of the main loop in Bellman–Ford have completed, at least <i>n</i>+1 of the shortest-path distances in <i>dist</i> are correct. (We consider all pairs of vertices to be connected, so that all "missing" edges are assigned a weight of positive infinity.)

@@ Line 1: / Line 1: @@
 The '''Bellman-Ford algorithm''' finds [[Shortest_path#Single-source_shortest_paths|single-source shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) When single-source shortest paths are all that which is needed, and not [[Shortest path#All-pairs_shortest_paths|all-pairs shortest paths]], The Bellman–Ford algorithm, with time complexity <math>\mathcal{O}(VE)</math>, outperforms the [[Floyd–Warshall algorithm]] at <math>\mathcal{O}(V^3)</math> in sparse graphs. It may also be combined with Dijkstra's algorithm to yield [[Johnson's algorithm]], which again outperforms Floyd–Warshall in sparse graphs.
-==The algorithm==
-The idea behind the algorithm is very easy to understand, and may be satisfactorily illustrated by the following pseudocode:
-<pre>
 input G,v
 for each u ∈ V(G)

@@ Line 24: / Line 24: @@
 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.
-* 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.

@@ Line 23: / Line 23: @@
 ===Proof of correctness for graphs containing no negative-weight cycles===
 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.