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.
Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report the negative cycle.
Algorithm
Like Dijkstra's algorithm, Bellman–Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path. However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this times, where is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra. The intermediate answers depend on the order of edges relaxed, but the final answer remains the same.
Bellman–Ford runs in time, where and are the number of vertices and edges respectively.
function BellmanFord(list vertices, list edges, vertex source) is
// This implementation takes in a graph, represented as
// lists of vertices (represented as integers [0..n-1]) and edges, // and fills two arrays (distance and predecessor) holding // the shortest path from the source to each vertex
distance := list of size n
predecessor := list of size n
// Step 1: initialize graph
for each vertex v in vertices do
// Initialize the distance to all vertices to infinity
distance[v] := inf
// And having a null predecessor
predecessor[v] := null
// The distance from the source to itself is, of course, zero
distance[source] := 0
// Step 2: relax edges repeatedly
repeat |V|−1 times: for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then distance[v] := distance[u] + w predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges do
if distance[u] + w < distance[v] then
predecessor[v] := u
// A negative cycle exist; find a vertex on the cycle
visited := list of size n initialized with false
visited[v] := true
while not visited[u] do
visited[u] := true
u := predecessor[u]
// u is a vertex in a negative cycle, find the cycle itself
ncycle := [u]
v := predecessor[u]
while v != u do
ncycle := concatenate([v], ncycle) v := predecessor[v] error "Graph contains a negative-weight cycle", ncycle return distance, predecessor
Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value.
The core of the algorithm is a loop that scans across all edges at every loop. For every , at the end of the -th iteration, from any vertex , following the predecessor trail recorded in yields a path that has a total weight that is at most , and further, is a lower bound to the length of any path from source to that uses at most edges.