Bellman-Ford Algorithm
Bellman-Ford Algorithm for Shortest Path · Also known as: Bellman-Ford method, Bellman algorithm
The Bellman-Ford Algorithm, developed by Richard Bellman and Lester R. Ford in the 1950s, is a fundamental algorithm for computing shortest paths in weighted graphs that may contain negative edge weights. Unlike Dijkstra's algorithm, it correctly handles negative weights and can detect the presence of negative-weight cycles.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Apply the Bellman-Ford algorithm when computing shortest paths in graphs with negative edge weights. It is essential for currency arbitrage detection, network protocols where weights can be negative, and any application where negative costs or weights are meaningful. Use Dijkstra's algorithm if all weights are non-negative, as it is more efficient. For detecting negative cycles without computing paths, this algorithm is also appropriate.
Strengths & limitations
- Handles graphs with negative edge weights correctly
- Detects negative-weight cycles, preventing erroneous shortest path results
- Simpler to understand and implement than some advanced shortest path algorithms
- Guaranteed to find shortest paths in O(VE) time
- Works on both directed and undirected graphs (with caution on undirected)
- Slower than Dijkstra for non-negative weights: O(VE) versus O((V+E)logV)
- Less efficient for sparse graphs compared to other algorithms
- Requires all edges to be explicitly listed, making it less suitable for implicit or dynamic graphs
- No heuristic guidance available to speed up computation
Frequently asked
Why does the algorithm need exactly V-1 iterations?
Any path in a graph with V vertices has at most V-1 edges. By iterating V-1 times, the algorithm allows distance information to propagate through the entire graph. A V-th iteration will only improve distances if a negative cycle exists.
How can the algorithm detect negative cycles?
After completing V-1 iterations, run one more relaxation pass. If any distance decreases, a negative cycle exists. The nodes involved in the cycle can be identified through backtracking using predecessor pointers.
What is the time complexity and how does it compare to Dijkstra?
Bellman-Ford runs in O(VE) time, where V is vertices and E is edges. Dijkstra runs in O((V+E)logV) with a binary heap. Bellman-Ford is slower but handles negative weights; Dijkstra is faster but requires non-negative weights.
Can Bellman-Ford work on undirected graphs with negative weights?
Technically yes, but it can create spurious negative cycles due to the bidirectional nature of edges. Special care is needed to interpret results correctly. For undirected graphs, consider alternative approaches.
Sources
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. DOI: 10.1090/qam/102435 ↗
- Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923. link ↗
How to cite this page
ScholarGate. (2026, June 3). Bellman-Ford Algorithm for Shortest Path. ScholarGate. https://scholargate.app/en/operations-research/bellman-ford-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- A-star Search AlgorithmOperations Research↔ compare
- Dijkstra AlgorithmOperations Research↔ compare
- Ford-Fulkerson AlgorithmOperations Research↔ compare