The Bellman–Ford algorithm is an algorithm for solving the single-source shortest-path problem in a weighted graph. Given a source vertex, it computes the minimum total edge weight needed to reach every other vertex, provided the relevant distances are not made unbounded below by a reachable negative-weight cycle. Unlike Dijkstra’s algorithm, it permits negative edge weights. Its standard implementation repeatedly relaxes all edges and can detect whether a negative-weight cycle is reachable from the source.
Problem and assumptions
Let be a directed graph with a finite vertex set , edge set , and edge-weight function . Let be the source.
The weight of a route is the sum of its edge weights. The shortest-path distance is conventionally understood as the infimum of the weights of all directed walks from to . Three outcomes are possible:
- Finite distance: a minimum-weight route exists.
- Unreachable vertex: no route exists, represented by .
- Unbounded-below distance: a negative-weight cycle can be reached from , and can be reached from that cycle, so repeating the cycle makes the route weight arbitrarily small. This is represented mathematically by .
A negative-weight cycle is a directed cycle whose edge weights sum to a negative number. Negative edges alone do not prevent finite shortest paths.
The standard Bellman–Ford procedure either returns distances when no negative cycle is reachable from , or reports a reachable negative cycle. An extended implementation can also identify exactly which vertices have distance .
For an undirected graph represented by two oppositely directed edges per connection, any negative-weight edge creates a negative closed walk: it can be traversed in both directions repeatedly. Consequently, negative edges in undirected graphs require particular care when interpreting the problem.
Relaxation
The algorithm maintains a tentative distance for every vertex and, optionally, a predecessor for reconstructing routes.
Initially,
To relax an edge , the algorithm checks whether reaching and then following that edge improves the current distance to :
then it sets
A relaxation never increases a tentative distance. Every finite value produced corresponds to the weight of an actual walk from the source. The difficulty is determining how many repetitions are sufficient to propagate all necessary improvements.
Dynamic-programming interpretation
Bellman–Ford can be understood through dynamic programming. Let be the minimum weight of a walk from to using at most edges. Then
and
A direct implementation of this recurrence uses a previous-round array and a current-round array.
The common implementation instead updates one distance array in place while scanning the edges. Consequently, an improvement may propagate through several edges during a single pass, depending on edge order. Its values after pass need not equal , but they are at least as good: every shortest route using at most edges has been accounted for by the end of that pass.
If no negative cycle is reachable from the source, any walk can have its cycles removed without increasing its weight. A shortest route can therefore be chosen to be simple, containing at most edges. This explains the algorithm’s standard pass limit.
Standard procedure
The following pseudocode uses in-place relaxation and stops early if an entire pass makes no change:
BellmanFord(V, E, w, s):
for each vertex v in V:
d[v] = infinity
predecessor[v] = none
d[s] = 0
for i = 1 to |V| - 1:
changed = false
for each edge (u, v) in E:
if d[u] != infinity and d[u] + w(u, v) < d[v]:
d[v] = d[u] + w(u, v)
predecessor[v] = u
changed = true
if not changed:
return d, predecessor
for each edge (u, v) in E:
if d[u] != infinity and d[u] + w(u, v) < d[v]:
return "negative-weight cycle reachable from source"
return d, predecessor
The final scan tests for an improvement; it need not actually update the distances. Early termination is valid because a complete pass without changes establishes that every edge already satisfies its relaxation inequality.
When finite distances have been obtained, a route to a reachable target can be reconstructed by following predecessors backward to and reversing the resulting sequence.
Correctness
Two central properties explain the algorithm’s correctness.
First, every finite tentative distance is the weight of some source-to-vertex walk. Thus, where the true shortest-path distance is finite, a tentative value cannot be smaller than it.
Second, after complete passes, the algorithm has found values no greater than the weights of all source-to-vertex routes using at most edges. This can be established inductively along each route and expressed as a loop invariant.
If no reachable negative cycle exists, each reachable vertex has a shortest simple path with at most edges. After that many passes, the two properties force each tentative distance to equal the corresponding shortest-path distance.
Why an extra improvement signals a negative cycle
After passes, any remaining successful relaxation implies the existence of a reachable negative cycle. Without such a cycle, shortest simple paths would already provide the final distances.
Conversely, suppose a reachable negative cycle exists. All its vertices become reachable in the distance labels after enough passes. If none of its edges could be relaxed, each cycle edge would satisfy
Adding these inequalities around the cycle cancels the distance terms and gives
contradicting the cycle’s negative total weight.
The reachability condition matters: a negative cycle in a disconnected or otherwise unreachable part of the graph does not affect a run from .
Worked example
Consider the directed edges
Using the synchronous dynamic-programming formulation, the distance table is:
| Maximum edges allowed | ||||
|---|---|---|---|---|
| 0 | 0 | |||
| 1 | 0 | 4 | 5 | |
| 2 | 0 | 4 | 2 | 8 |
| 3 | 0 | 4 | 2 | 5 |
The shortest route to is
with total weight
An in-place implementation may obtain these final values sooner if its edge order allows improvements to propagate within the same pass.
If an edge of weight is added, then the cycle
has total weight . Because it is reachable from , the distances to , , and become unbounded below. The distance to remains , because the graph provides no route from that cycle back to .
Complexity and implementation issues
The standard algorithm makes up to full edge scans and one additional detection scan. Its usual worst-case time complexity is stated as
Including initialization explicitly, a bound valid even for graphs with no edges is
An edge-list representation is sufficient. Distance and predecessor arrays require auxiliary space, excluding storage for the graph. Storing all dynamic-programming rounds is unnecessary unless intermediate results are required.
Important implementation details include:
- Infinity handling: an unreachable source endpoint must be skipped before adding an edge weight. A finite sentinel used as “infinity” must not accidentally participate in arithmetic.
- Overflow: even when individual edge weights fit in an integer type, path sums may not.
- Floating-point arithmetic: rounding can alter comparisons and make cycles with totals close to zero difficult to classify. Using a tolerance changes the exact mathematical detection criterion.
- Edge order: ordering can substantially change the number of passes before convergence, although it does not change the worst-case guarantee.
- Strict updates: predecessors should normally change only when a strictly shorter distance is found. Updating predecessors on ties can complicate reconstruction.
Locating cycles and affected vertices
To extract a negative cycle, an implementation can perform actual relaxations in an additional pass and record an updated vertex. Following its predecessor pointer times reaches a vertex on a predecessor cycle; continuing until a vertex repeats recovers the cycle, with the traversal reversed to obtain its directed order.
To identify all vertices whose distances are , the algorithm can collect vertices improved during the additional pass and traverse forward from them using breadth-first search or depth-first search. This marks both the reachable negative cycles and their downstream vertices. Other reachable vertices can still have finite shortest-path distances.
Applications and related algorithms
Difference constraints
Bellman–Ford can test feasibility of inequalities of the form
Represent each inequality by an edge of weight , and add a new source with zero-weight edges to every vertex. A negative cycle indicates inconsistency, because summing the inequalities around it yields an impossible inequality. If no negative cycle exists, the computed distances provide a feasible assignment.
This connects the algorithm to mathematical optimization and constraint-based scheduling.
Routing
Bellman–Ford’s recurrence underlies distance-vector routing. Routers exchange distance estimates with neighbors and update their estimates by combining a link cost with a neighbor’s advertised distance.
Such protocols are distributed adaptations rather than literal executions of a centralized edge-scanning program. Their behavior under network changes introduces additional issues, including routing loops and the count-to-infinity problem. This is an important application in distributed computing.
Reweighting and arbitrage
Johnson’s algorithm uses Bellman–Ford to compute vertex potentials and detect negative cycles before reweighting a graph for repeated Dijkstra searches. The reweighted edges are nonnegative while shortest-path relationships are preserved.
Currency-exchange arbitrage can also be modeled using negative-cycle detection. Assigning an exchange rate the weight transforms a cycle whose rate product exceeds into a negative-weight cycle. Practical models must additionally account for transaction costs, numerical precision, and execution constraints.
Alternatives
Dijkstra’s algorithm is generally preferable when all edge weights are nonnegative. In a directed acyclic graph, topological-order relaxation finds shortest paths in time even with negative weights.
Queue-based variants process vertices whose distance changes may enable further relaxations. These can avoid many unnecessary scans in practice, but the commonly used shortest-path faster algorithm variant still has worst-case time.
Historical development
The algorithm is named after Richard Bellman and Lester R. Ford Jr. Ford described a related method in 1956, and Bellman published his dynamic-programming formulation in 1958. Edward F. Moore independently presented a related shortest-path method in 1959, accounting for the alternative name Bellman–Ford–Moore algorithm.
These formulations established repeated relaxation as a central technique for shortest-path computation, connecting graph algorithms, dynamic programming, and distributed routing.