Bellman–Ford Algorithm
Bellman–Ford Algorithm is a GFG problem (Medium). It solves the bellman ford shortest path problem: the shortest distance from one source vertex to every other vertex in a weighted directed graph, and unlike Dijkstra it works when edges have negative weights.
- The input is a vertex count
V, a list of directed edges[u, v, w], and a sourcesrc. - It returns the distance to each vertex, with unreachable vertices left at infinity.
- If the graph contains a negative cycle reachable from the source, no shortest path exists, because going round the cycle again is always cheaper. The algorithm reports that instead of returning distances.
The cost is O(V·E), which is slower than Dijkstra's O(E log V). Negative weights are what you pay that for.
- 1 <= V <= 500
- 0 <= E <= 10⁴
- -10⁴ <= weight <= 10⁴
- Edge weights may be negative; a negative cycle is reported rather than solved
Intuition
Dijkstra settles the nearest unfinished vertex and never looks at it again, which is only safe when no edge can lower a distance later. One negative edge breaks that, so Bellman-Ford gives up on clever ordering entirely and just relaxes every edge, over and over.
That plainness buys two guarantees:
- Correct after
V - 1passes. Afterkfull passes every shortest path using at mostkedges is right, and a shortest path never repeats a vertex, so it has at mostV - 1edges. - Free cycle detection. Since
V - 1passes are provably enough, aV-th pass can change nothing in an honest graph. If it does, there is a negative cycle.
Reach for Bellman-Ford when edge weights can be negative, or when the question is whether a negative cycle exists at all, such as currency arbitrage. If every weight is non-negative, Dijkstra is strictly faster. If you need distances between every pair rather than from one source, Floyd-Warshall is the O(V³) answer.
Approach
Before reading on, work a small bellman ford algorithm example by hand: take a four-vertex chain 0→1→2→3 and relax the edges in the order 2→3, 1→2, 0→1. Count how many passes it takes for the distance to reach vertex 3, and you will see why the bound is a number of passes rather than a clever order.
Start every distance at infinity but the source
Set dist[src] = 0 and all the rest to infinity. No priority queue and no visited set appear anywhere, and that plainness is exactly what lets negative weights be handled: nothing is ever declared final early.
Relax every edge, V-1 times over
A pass walks the whole edge list and, for each [u, v, w], lowers dist[v] to dist[u] + w when that is better. The order of edges inside a pass does not matter, because correctness comes from how many passes run, not from their sequence.
Never relax out of an unreachable vertex
Only use an edge when dist[u] is not still infinity:
- Python:
inf + wstays infinite and is harmless. - C++ and Java: a large sentinel integer is used instead, and adding a negative weight to it overflows into a small number that floods the array with invented paths.
Negative cycle detection with one more pass
Run pass number V. If any edge still relaxes, some route can be made cheaper forever by looping, so report the negative cycle instead of returning distances.
Stop early when a pass changes nothing
Track whether any distance moved during a pass and break out if none did, because further passes cannot change anything either. The worst case stays O(V·E), but most real graphs settle long before the bound.
Bellman–Ford Algorithm solution in Python | C++ | Java
Common pitfalls
Relaxing out of a vertex that is still unreachable
if dist[u] + w < dist[v]:
if dist[u] != INF and dist[u] + w < dist[v]:
Python's inf + w stays infinite, so it happens to be safe there, but C++ and Java use a large sentinel integer. Adding a negative weight to it gives a small number that looks like a real distance, and the bogus value then spreads to the rest of the graph.
Skipping the extra detection pass
return dist
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return None
return distAfter V - 1 passes every genuine shortest path is settled, so a further improvement can only come from a cycle of negative total weight. Without the check you return numbers that no path actually achieves.
Running the passes a vertex short
for _ in range(n - 2):
for _ in range(n - 1):
A shortest path can span V - 1 edges, and a pass only guarantees one more edge's worth of correctness. On a chain through every vertex, one pass too few leaves the last distance unsettled.
Edge cases
The V-th pass still improves an edge, so the algorithm reports the cycle; the distances are meaningless because they can be driven down forever.
Its distance stays at infinity, and the guard stops any edge leaving it from inventing a path.
Handled normally. Later passes lower the distances that the negative edge improves, which is the case Dijkstra gets wrong.