Bellman-Ford algorithm
Encyclopedia
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.
For graphs with only non-negative edge weights, the faster Dijkstra's algorithm
also solves the problem.
Thus, Bellman–Ford is used primarily for graphs with negative edge weights.
The algorithm is named after its developers, Richard Bellman
and Lester Ford, Jr.
If a graph contains a "negative cycle", i.e., a cycle
whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed, i.e., there may be no shortest path. Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is reachable from the source.
According to Robert Sedgewick
, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortest-paths problems". Let G be a graph containing a negative cycle. One NP-Complete
variant of the shortest-path problem asks for the shortest path in G (containing a negative cycle) such that no edge is repeated. Sedgewick gives a reduction
from the Hamiltonian path problem
to this variant of the problem.
, but instead of greedily
selecting the minimum-weight 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 negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
Proof. For the base case of induction, consider
For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by
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 i-1 edges. By inductive assumption,
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],
Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving
I.e., every cycle has nonnegative weight.
s, 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 as follows:
For graphs with only non-negative edge weights, the faster Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
also solves the problem.
Thus, Bellman–Ford is used primarily for graphs with negative edge weights.
The algorithm is named after its developers, Richard Bellman
Richard Bellman
Richard Ernest Bellman was an American applied mathematician, celebrated for his invention of dynamic programming in 1953, and important contributions in other fields of mathematics.-Biography:...
and Lester Ford, Jr.
L. R. Ford, Jr.
Lester Randolph Ford, Jr. is an American mathematician specializing in network flow problems. He is the son of mathematician Lester R. Ford, Sr..Ford's paper with D. R...
If a graph contains a "negative cycle", i.e., a cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed, i.e., there may be no shortest path. Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is reachable from the source.
According to Robert Sedgewick
Robert Sedgewick (computer scientist)
Robert Sedgewick is a computer science professor at Princeton University and a member of the board of directors of Adobe Systems....
, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortest-paths problems". Let G be a graph containing a negative cycle. One NP-Complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
variant of the shortest-path problem asks for the shortest path in G (containing a negative cycle) such that no edge is repeated. Sedgewick gives a reduction
Reduction (complexity)
In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
from the Hamiltonian path problem
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
to this variant of the problem.
Algorithm
Bellman–Ford is in its basic structure very similar to Dijkstra's algorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
, but instead of greedily
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
selecting the minimum-weight 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
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(|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 negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
Proof of correctness
The correctness of the algorithm can be shown by inductionMathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
- If Distance(u) is not infinity, it is equal to the length of some path from s to u;
- 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
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 i-1 edges. By inductive assumption,
v.distance after i−1 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 ith 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 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],
v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weightSumming around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weightI.e., every cycle has nonnegative weight.
Applications in routing
A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocolDistance-vector routing protocol
In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of routing protocols, the other major class being the link-state protocol...
s, for example the Routing Information Protocol
Routing Information Protocol
The Routing Information Protocol is a distance-vector routing protocol, which employs the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from the source to a destination. The maximum number of hops allowed for RIP is 15....
(RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system
Autonomous system (Internet)
Within the Internet, an Autonomous System is a collection of connected Internet Protocol routing prefixes under the control of one or more network operators that presents a common, clearly defined routing policy to the Internet....
, a collection of IP networks typically owned by an ISP.
It consists of the following steps:
- Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
- Each node sends its table to all neighboring nodes.
- 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 topologyNetwork topologyNetwork topology is the layout pattern of interconnections of the various elements of a computer or biological network....
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).