Class  Singlesource shortest path problem (for weighted directed graphs) 

Data structure  Graph 
Worst case performance  O(  V   E  ) 
Worst case space complexity  O(  V  ) 
The Bellman–Ford algorithm, a labelcorrecting algorithm,^{[1]} computes singlesource shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm solves the same problem with a lower running time, but requires edge weights to be nonnegative. Thus, Bellman–Ford is usually used only when there are negative edge weights. The algorithm was developed by Richard Bellman and Lester Ford, Jr.
According to Robert Sedgewick, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortestpaths problems",^{[2]} and he gives the specific example of a reduction from the NPcomplete Hamilton path problem to the shortest paths problem with general weights. If a graph contains a cycle of total negative weight then arbitrarily low weights are achievable and so there's no solution; BellmanFord detects this case.
If the graph does contain a cycle of negative weights, BellmanFord can only detect this; BellmanFord cannot find the shortest path that does not repeat any vertex in such a graph. This problem is at least as hard as the NPcomplete longest path problem.
Contents 
Bellman–Ford is in its basic structure very similar to Dijkstra's algorithm, but instead of greedily selecting the minimumweight node not yet processed to relax, it simply relaxes all the edges, and does this V − 1 times, where V is the number of vertices in the graph. The repetitions allow minimum distances to accurately propagate throughout the graph, since, in the absence of negative cycles, the shortest path can only visit each node at most once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.
Bellman–Ford runs in O(V·E) time, where V and E are the number of vertices and edges respectively.
procedure BellmanFord(list vertices, list edges, vertex source) // This implementation takes in a graph, represented as lists of vertices // and edges, and modifies the vertices so that their distance and // predecessor attributes store the shortest paths. // Step 1: Initialize graph for each vertex v in vertices: if v is source then v.distance := 0 else v.distance := infinity v.predecessor := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)1: for each edge uv in edges: // uv is the edge from u to v u := uv.source v := uv.destination if u.distance + uv.weight < v.distance: v.distance := u.distance + uv.weight v.predecessor := u // Step 3: check for negativeweight cycles for each edge uv in edges: u := uv.source v := uv.destination if u.distance + uv.weight < v.distance: error "Graph contains a negativeweight cycle"
The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
Proof. For the base case of induction, consider i=0
and the moment before for cycle is executed for the first time. Then, for the source vertex, source.distance = 0
, which is correct. For other vertices u, u.distance = infinity
, 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 v.distance := u.distance + uv.weight
. By inductive assumption, u.distance
is the length of some path from source to u. Then u.distance + uv.weight
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 the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i1 edges. By inductive assumption, v.distance
after i1 cycles is at most the length of this path. Therefore, uv.weight + v.distance
is at most the length of the path from s to u. In the i^{th} cycle, u.distance
gets compared with uv.weight + v.distance
, and is set equal to it if uv.weight + v.distance
was smaller. Therefore, after i cycles, u.distance
is at most the length of the shortest path from source to u that uses at most i edges.
If there are no negativeweight 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[k1],
v[i].distance <= v[i1 (mod k)].distance + v[i1 (mod k)]v[i].weight
Summing around the cycle, the v[i].distance terms and the v[i1 (mod k)] distance terms cancel, leaving
0 <= sum from 1 to k of v[i1 (mod k)]v[i].weight
I.e., every cycle has nonnegative weight.
A distributed variant of the Bellman–Ford algorithm is used in distancevector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:
The main disadvantages of the Bellman–Ford algorithm in this setting are
In a 1970 publication, Yen^{[3]} described an improvement to the Bellman–Ford algorithm for a graph without negativeweight cycles. Yen's improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into one of two subsets. The first subset, E_{f}, contains all edges (v_{i}, v_{j}) such that i < j; the second, E_{b}, contains edges (v_{i}, v_{j}) such that i > j. Each vertex is visited in the order v_{1}, v_{2},...,v_{V}, relaxing each outgoing edge from that vertex in E_{f}. Each vertex is then visited in the order v_{V}, v_{V1},...,v_{1}, relaxing each outgoing edge from that vertex in E_{b}. Yen's improvement effectively halves the number of "passes" required for the singlesourceshortestpath solution.
