View source for Bellman–Ford algorithm

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)
     let dist[u] = ∞
let dist[v] = 0
for each i ∈ [1..V-1]
     for each (u,w) ∈ E(G)
          dist[w] = min(dist[w],dist[u]+wt(u,w))
for each (u,w) ∈ E(G)
     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.

==Theory of the algorithm==

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.)

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

===Proof of detection of negative-weight cycles===
Suppose vertices <math>v_0, v_1,..., v_{n-1}</math> vertices form a negative-weight cycle, that at some point their entries in the <i>dist</i> array are <math>d_0, d_1,\ldots, d_{n-1}</math>, and that the numbers <math>w_0, w_1,\ldots, w_{n-1}</math> represent the weights of edges in the cycle, where <math>w_i</math> is the weight of the edge from <math>v_i</math> to <math>v_{i+1}</math>. Now, because the cycle has negative weight, we know that <math>w_0+w_1+\ldots+w_{n-1}<0</math>. We show by contradiction that it is always possible to relax one of the edges.<br/>
<br/>
Suppose we assume the opposite: that there exists no <math>i</math> such that <math>d_i + w_i < d_{i+1}</math>. Then, we have <math>d_0 + w_0 \ge d_1, d_1 + w_1 \ge d_2,\ldots, d_{n-1} + w_{n-1} \ge d_0</math>. Adding yields <math>(d_0 + d_1 + \ldots + d_{n-1}) + (w_0 + w_1 + \ldots + w_{n-1}) \ge (d_0 + d_1 + \ldots + d_{n-1})</math>, which, after cancelling the <math>d</math>'s, is a contradiction. So our assumption must be false, and it must always be possible to relax at least one of the edges in a negative-weight cycle. Thus, if there is a negative-weight cycle, it will always be detected at the end of the algorithm, because at least one edge on that cycle must be capable of relaxation.

==References==
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman-Ford algorithm, pp.588–592.

[[Category:Algorithms]]
[[Category:Graph theory]]