# Bellman–Ford algorithm

The **Bellman–Ford algorithm** is an algorithm for the single-source shortest-path problem in weighted, directed graphs whose edge weights may be negative, and it also detects negative-weight cycles reachable from the source, a case in which shortest paths are not defined. It runs in \( O(V \cdot E) \) time for a graph with \( V \) vertices and \( E \) edges, slower than [Dijkstra's algorithm](https://www.edgepedia.org/dijkstras-algorithm) but correct on inputs where Dijkstra fails.<sup>[1](https://xlinux.nist.gov/dads/HTML/bellmanford.html)</sup><sup> • </sup><sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>

| Key fact | Detail |
|---|---|
| Problem solved | Single-source shortest paths in directed graphs with real-valued, possibly negative edge weights<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup> |
| Running time | \( O(V \cdot E) \); space \( O(V) \)<sup>[1](https://xlinux.nist.gov/dads/HTML/bellmanford.html)</sup><sup> • </sup><sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup> |
| Structure | \( V-1 \) passes relaxing every edge, then one extra pass to detect negative cycles<sup>[1](https://xlinux.nist.gov/dads/HTML/bellmanford.html)</sup> |
| Negative cycles | Returns false (or raises an exception in implementations such as NetworkX) if a negative-weight cycle is reachable from the source<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup><sup> • </sup><sup>[4](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html)</sup> |
| Origin | Bellman's 1958 RAND paper "On a Routing Problem"; Ford's 1956 RAND report on network flow theory<sup>[5](https://www.cs.yale.edu/homes/lans/readings/routing/bellman-routing-1958.pdf)</sup><sup> • </sup><sup>[6](https://dml.cz/bitstream/handle/10338.dmlcz/401175/DejinyMat_25-2004-1_7.pdf)</sup> |
| Applications | Distance-vector routing (RIP), currency arbitrage detection, difference constraints, reweighting inside Johnson's algorithm<sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup> |
| Modern status | The \( O(n \cdot m) \) bound stood for over 65 years until Fineman's 2024 \( \tilde{O}(mn^{8/9}) \) algorithm<sup>[7](https://arxiv.org/abs/2607.19346)</sup> |

## The problem it addresses

Dijkstra's algorithm computes shortest paths from one source to every other vertex, but its correctness rests on the assumption that all edge weights are non-negative. When an edge can subtract from a path's total weight, a negative edge can improve a vertex that Dijkstra has already settled, and the algorithm returns wrong answers without any warning.<sup>[8](https://dsamindmap.com/compare/dijkstra-vs-bellman-ford)</sup><sup> • </sup><sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup>

Negative weights are not a mathematical curiosity. A cost model with credits, a rebate, or a currency conversion that profits all produce them. Bellman–Ford handles them correctly, and it performs a second service: it determines when "shortest path" has stopped being a meaningful question. If a cycle with negative total weight is reachable from the source, a path can pass through the cycle repeatedly and grow arbitrarily cheap, so no finite shortest path exists.<sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup><sup> • </sup><sup>[4](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html)</sup>

## How the algorithm works

The algorithm uses relaxation, the same operation Dijkstra uses. Each vertex \( v \) carries an estimate \( d[v] \) of the shortest-path weight from the source \( s \). Relaxing an edge \( (u, v) \) tests whether \( d[v] > d[u] + w(u, v) \); if so, the estimate and the predecessor pointer are updated. Estimates only decrease, and they converge to the true shortest-path weights.<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>

The procedure, as given in the CLRS-style presentation, is:<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>

1. Initialize: set \( d[s] = 0 \) and \( d[v] = \infty \) for every other vertex.<sup>[1](https://xlinux.nist.gov/dads/HTML/bellmanford.html)</sup>
2. Repeat \( |V| - 1 \) times: relax every edge of the graph once per pass.<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>
3. Check every edge once more. If any edge \( (u, v) \) still satisfies \( d[v] > d[u] + w(u, v) \), a negative-weight cycle reachable from the source exists, and the algorithm reports failure; otherwise it returns the distances and the shortest-paths tree.<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>

**Why \( V-1 \) passes suffice.** A shortest path, when no negative cycle is reachable, is simple and therefore contains at most \( |V| - 1 \) edges. After \( i \) passes, the estimates are correct for every vertex whose shortest path uses at most \( i \) edges, because each pass extends correctness by at least one more edge along any shortest path. After \( |V| - 1 \) passes every reachable vertex is settled. The final pass then detects negative cycles: if some edge can still be relaxed, distances were not yet stable, which is possible only when a negative cycle keeps lowering them.<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup><sup> • </sup><sup>[9](https://dsa.handbook.academy/patterns/shortest-paths-decision-tree/)</sup>

The running time follows directly: initialization takes \( O(V) \), each of the \( |V| - 1 \) passes takes \( O(E) \), and the final check takes \( O(E) \), for \( O(V \cdot E) \) total.<sup>[2](https://bobson.ludost.net/books/algo/book6/chap25.htm)</sup>

**Scope of the detection.** The standard single-source version detects only negative cycles reachable from the chosen source. A negative cycle in a component the source cannot reach goes undetected; for all-pairs coverage one can run Floyd–Warshall and inspect its diagonal.<sup>[4](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html)</sup><sup> • </sup><sup>[9](https://dsa.handbook.academy/patterns/shortest-paths-decision-tree/)</sup>

## History

The algorithm carries two names because two [RAND Corporation](https://www.edgepedia.org/rand-corporation) researchers produced closely related methods in the 1950s. L. R. Ford Jr.'s algorithm arose within network flow theory and was first published in the RAND Corporation Paper P–923 in 1956.<sup>[6](https://dml.cz/bitstream/handle/10338.dmlcz/401175/DejinyMat_25-2004-1_7.pdf)</sup><sup> • </sup><sup>[10](https://bibbase.org/network/publication/ford-networkflowtheory-1956)</sup> [Richard Bellman](https://www.edgepedia.org/richard-bellman)'s paper "On a Routing Problem" (1958) treated the problem of finding a minimum-time route among cities whose travel times vary with road quality and traffic, and applied the functional-equation technique of dynamic programming, combined with approximation in policy space, to obtain an iterative method converging after at most \( N - 1 \) iterations.<sup>[5](https://www.cs.yale.edu/homes/lans/readings/routing/bellman-routing-1958.pdf)</sup> Edward F. Moore's independent work gives the variant often called Bellman–Ford–Moore.<sup>[7](https://arxiv.org/abs/2607.19346)</sup>

A 2016 result in *Theoretical Computer Science* showed that the classical Bellman–Ford–Moore algorithm is optimal for the shortest \( s \)-\( t \) path problem if only Min and Sum operations are allowed, so its long tenure is not merely historical inertia.<sup>[11](https://www.sciencedirect.com/science/article/pii/S0304397516002073)</sup>

## Applications

**Distance-vector routing.** Routers running distance-vector protocols execute a distributed form of Bellman–Ford against their neighbors. The [Routing Information Protocol](https://www.edgepedia.org/routing-information-protocol) (RIP), specified in RFC 1058 (1988), is the classic example: each router advertises its distances, and the protocol's metric is an integer between 1 and 15, with networks limited to a longest path of 15 hops. RIP's "counting to infinity" behavior for resolving lost routes reflects the same iterative relaxation at the network's heart.<sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup><sup> • </sup><sup>[12](https://www.rfc-editor.org/rfc/pdfrfc/rfc1058.txt.pdf)</sup>

**Currency arbitrage.** If exchange rates are converted to logarithms, a sequence of trades that returns a profit corresponds to a cycle of negative total weight in the log-space graph. Running Bellman–Ford and checking the final pass finds exactly such exploitable loops.<sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup>

**Difference constraints and reweighting.** Systems of difference constraints of the form \( x_j - x_i \le c \) map onto shortest-path problems with negative weights. Bellman–Ford also sits inside Johnson's algorithm for all-pairs shortest paths: it runs once from a virtual source to compute a per-vertex potential, producing a reweighted graph with non-negative edges on which the faster Dijkstra can then be run from every vertex.<sup>[3](https://prism.nicofortuin.com/algorithms/bellman-ford/)</sup><sup> • </sup><sup>[9](https://dsa.handbook.academy/patterns/shortest-paths-decision-tree/)</sup>

## Comparison with Dijkstra's algorithm

The two algorithms solve the same single-source problem with opposite tradeoffs.<sup>[8](https://dsamindmap.com/compare/dijkstra-vs-bellman-ford)</sup>

| Dimension | Dijkstra | Bellman–Ford |
|---|---|---|
| Time (with heap) | \( O(E \log V) \) | \( O(V \cdot E) \) |
| Negative weights | Incorrect, silently | Correct |
| Negative-cycle detection | Not possible | One extra pass |
| Approach | Greedy, settles nodes in order | Repeated relaxation of all edges |
| Data structure | Priority queue | Plain edge list |

For sparse graphs, where \( E \) is close to \( V \), Bellman–Ford runs in roughly \( O(V^2) \) against Dijkstra's \( O(V \log V) \), so the generality is bought at a real price. Bellman–Ford can stop early if a full pass changes no distance, though it lacks Dijkstra's ability to halt once a target vertex is settled.<sup>[8](https://dsamindmap.com/compare/dijkstra-vs-bellman-ford)</sup><sup> • </sup><sup>[13](https://waggertron.github.io/tech-learning/topics/cs/named-algorithms/bellman-ford/)</sup>

## Variants and practical performance

The plain algorithm wastes work when a pass changes nothing. The **Shortest Path Faster Algorithm** (SPFA), sometimes described as "Bellman-Ford with a queue", re-processes only vertices whose distance recently improved, which speeds up typical instances while keeping the same worst-case bound.<sup>[13](https://waggertron.github.io/tech-learning/topics/cs/named-algorithms/bellman-ford/)</sup> Empirical studies confirm the theoretical picture: Dijkstra performs best on sparse graphs, Floyd–Warshall and Dantzig's \( O(V^3) \) methods become competitive on dense graphs, and Bellman–Ford's \( O(V \cdot E) \) cost makes it the choice specifically when negative edges are present.<sup>[14](https://www.mdpi.com/2673-4591/100/1/31)</sup>

## Breaking the bound

For over 65 years the \( O(n \cdot m) \) worst-case bound of Bellman–Ford–Moore, with \( n \) vertices and \( m \) arcs, resisted improvement for general real-valued weights, though many heuristics beat it in practice without surpassing the theoretical limit.<sup>[7](https://arxiv.org/abs/2607.19346)</sup> In 2024, J. T. Fineman published a \( \tilde{O}(mn^{8/9}) \)-time algorithm for single-source shortest paths with negative real weights, the first asymptotic break of the bound; subsequent work refined the runtime further, and by 2026 randomized algorithms running in \( m^{1+o(1)} \) time, almost linear in the input size, were known.<sup>[7](https://arxiv.org/abs/2607.19346)</sup> These results change the theoretical landscape for negative-weight shortest paths, but Bellman–Ford remains the standard simple, exact method taught and implemented in general-purpose libraries: NetworkX, for example, exposes it as the method for graphs with negative edge weights and raises an exception when a negative cycle is found.<sup>[4](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html)</sup>

## References

1. [Bellman-Ford algorithm, Dictionary of Algorithms and Data Structures, NIST](https://xlinux.nist.gov/dads/HTML/bellmanford.html)
2. [Chapter 25: Single-Source Shortest Paths (Bellman-Ford), Introduction to Algorithms](https://bobson.ludost.net/books/algo/book6/chap25.htm)
3. [Bellman–Ford — visualized, explained, Prism](https://prism.nicofortuin.com/algorithms/bellman-ford/)
4. [bellman_ford_predecessor_and_distance, NetworkX 3.7 documentation](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html)
5. [Richard Bellman (1958). On a Routing Problem. Quarterly of Applied Mathematics](https://www.cs.yale.edu/homes/lans/readings/routing/bellman-routing-1958.pdf)
6. [The Bellman–Ford algorithm, historical note, Dejiny Matematiky](https://dml.cz/bitstream/handle/10338.dmlcz/401175/DejinyMat_25-2004-1_7.pdf)
7. [Bellman-Ford in Almost-Linear Time, arXiv](https://arxiv.org/abs/2607.19346)
8. [Dijkstra vs Bellman-Ford: Which to Use, DSA MindMap](https://dsamindmap.com/compare/dijkstra-vs-bellman-ford)
9. [Shortest paths decision tree, The DSA Handbook](https://dsa.handbook.academy/patterns/shortest-paths-decision-tree/)
10. [L. R. Ford Jr. (1956). Network flow theory, RAND Corporation](https://bibbase.org/network/publication/ford-networkflowtheory-1956)
11. [On the optimality of Bellman–Ford–Moore shortest path algorithm, Theoretical Computer Science](https://www.sciencedirect.com/science/article/pii/S0304397516002073)
12. [C. Hedrick (1988). RFC 1058: Routing Information Protocol](https://www.rfc-editor.org/rfc/pdfrfc/rfc1058.txt.pdf)
13. [Bellman-Ford algorithm, Here Be Dragons](https://waggertron.github.io/tech-learning/topics/cs/named-algorithms/bellman-ford/)
14. [A Performance Comparison of Shortest Path Algorithms in Directed Graphs, MDPI Engineering Proceedings](https://www.mdpi.com/2673-4591/100/1/31)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Computational graph problems and algorithms › Shortest-path problems and algorithms*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license