The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by , but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

Lemma. After i repetitions of for loop,

  • if Distance(u) is not infinity, it is equal to the length of some path from s to u; and
  • if there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.

Proof. For the base case of induction, consider <code>i=0</code> and the moment before for loop is executed for the first time. Then, for the source vertex, <code>source.distance = 0</code>, which is correct. For other vertices u, <code>u.distance = infinity</code>, which is also correct because there is no path from source to u with 0 edges.

For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by

<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 u 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<sup>th</sup> 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],

<code>v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight</code>

Summing around the cycle, the v[i].distance and v[i−1 (mod k)].distance terms cancel, leaving

<code>0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight</code>

I.e., every cycle has nonnegative weight.

Finding negative cycles

When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman–Ford algorithm can be used for applications in which this is the target to be sought – for example in cycle-cancelling techniques in network flow analysis. The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system (AS), a collection of IP networks typically owned by an ISP.

It consists of the following steps:

  1. Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
  2. Each node sends its table to all neighboring nodes.
  3. When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.

The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:

  • It does not scale well.
  • Changes in network topology are not reflected quickly since updates are spread node-by-node.
  • Count to infinity if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops.

Improvements

The Bellman–Ford algorithm may be improved in practice (although not in the worst case) by the observation that, if an iteration of the main loop of the algorithm terminates without making any changes, the algorithm can be immediately terminated, as subsequent iterations will not make any more changes. With this early termination condition, the main loop may in some cases use many fewer than iterations, even though the worst case of the algorithm remains unchanged. The following improvements all maintain the <math>O(|V|\cdot |E|)</math> worst-case time complexity.

A variation of the Bellman–Ford algorithm described by , reduces the number of relaxation steps that need to be performed within each iteration of the algorithm. If a vertex v has a distance value that has not changed since the last time the edges out of v were relaxed, then there is no need to relax the edges out of v a second time. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to a constant-factor savings in time for dense graphs. This variation can be implemented by keeping a collection of vertices whose outgoing edges need to be relaxed, removing a vertex from this collection when its edges are relaxed, and adding to the collection any vertex whose distance value is changed by a relaxation step. In China, this algorithm was popularized by Fanding Duan, who rediscovered it in 1994, as the "shortest path faster algorithm".

described another improvement to the Bellman–Ford algorithm. His improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into two subsets. The first subset, E<sub>f</sub>, contains all edges (v<sub>i</sub>, v<sub>j</sub>) such that i < j; the second, E<sub>b</sub>, contains edges (v<sub>i</sub>, v<sub>j</sub>) such that i > j. Each vertex is visited in the order , relaxing each outgoing edge from that vertex in E<sub>f</sub>. Each vertex is then visited in the order , relaxing each outgoing edge from that vertex in E<sub>b</sub>. Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match the correct shortest path distances: one from E<sub>f</sub> and one from E<sub>b</sub>. This modification reduces the worst-case number of iterations of the main loop of the algorithm from to <math>|V|/2</math>.

, at Georgetown University, created an improved algorithm that with high probability runs in <math>\tilde O(|V|^{8/9}\cdot |E|)</math> time. Here, the <math>\tilde O</math> is a variant of big O notation that hides logarithmic factors.

Notes

References

Original sources

Secondary sources

  • Section 22.1: The Bellman–Ford algorithm, pp.&nbsp;612–616. Problem 22–1, p.&nbsp;640.