Bellman-Ford
mediumAfter k passes, every shortest path using at most k edges is correct. A simple path uses at most V−1 edges - so if anything still improves on pass V, there is a negative cycle.
O(E) with early exitWorst O(V·E)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How bellman-ford works
Bellman-Ford abandons Dijkstra's greed. Instead of settling nodes one by one, it sweeps the entire edge list and relaxes anything that improves, then sweeps again. After pass k, every shortest path that uses at most k edges is correct - and since a simple path in a V-vertex graph has at most V-1 edges, V-1 passes settle everything.
Never committing is what buys negative-weight tolerance. A distance written in pass 2 can be overwritten in pass 5; no value is trusted until the passes end. The implementation here also exits early when a full pass changes nothing, since every later pass would be identical - the default run stops after its second pass.
The final sweep is a proof. If any edge still improves after V-1 passes, some path with V or more edges got cheaper, which forces a repeated vertex - a cycle - with negative total weight. Around such a cycle, cost decreases forever and shortest paths stop existing. That detection is the algorithm's second job.
Step by step
- The default directed graph has 8 vertices, and edge B to E carries weight -2. Only dist[A] is 0; everything else starts infinite.
- Pass 1 sweeps all 10 edges in list order. A to B writes 4, A to D writes 2, B to C writes 10.
- The negative edge fires: B to E writes dist[E] = 2, the 4 at B plus the -2 weight.
- Still in pass 1, E to F improves F to 6, beating the 12 written moments earlier via C. E to H writes 5.
- Pass 2 sweeps again and improves nothing, so the loop exits early - passes 3 through 7 are provably redundant.
- One final sweep checks every edge: no improvement anywhere, so no negative cycle. Distances are final: B 4, C 10, D 2, E 2, F 6, G 9, H 5.
Complexity
| Best case time | O(E) with early exit |
|---|---|
| Worst case time | O(V·E) |
| Space | O(V) |
V−1 relaxation passes, plus one more as a proof of no negative cycle.
Reference implementation
Python
def bellman_ford(vertices, edges, start):
dist = {v: float("inf") for v in vertices}
dist[start] = 0
for _ in range(len(vertices) - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # early exit: nothing left to relax
break
for u, v, w in edges: # a V-th improvement is impossible
if dist[u] + w < dist[v]: # unless there is a negative cycle
raise ValueError("negative cycle")
return distJavaScript
function bellmanFord(vertices, edges, start) {
const dist = new Map(vertices.map((v) => [v, Infinity]));
dist.set(start, 0);
for (let i = 0; i < vertices.length - 1; i++) {
let changed = false;
for (const [u, v, w] of edges) {
if (dist.get(u) + w < dist.get(v)) { dist.set(v, dist.get(u) + w); changed = true; }
}
if (!changed) break;
}
for (const [u, v, w] of edges) {
if (dist.get(u) + w < dist.get(v)) throw new Error("negative cycle");
}
return dist;
}Worth noticing
After k passes, every shortest path using ≤ k edges is correct
That is the invariant. A simple shortest path uses at most V−1 edges, so V−1 passes is enough - and this is why the loop count is what it is rather than an arbitrary choice.
It handles negative weights, and Dijkstra cannot
Bellman-Ford never commits to a distance being final, so a later improvement is always allowed. That is exactly the freedom Dijkstra gives up in exchange for its speed.
The extra pass is a proof, not a heuristic
If any edge still improves after V−1 passes, some path uses V or more edges and got shorter - which requires repeating a vertex on a cycle of negative total weight. There is no shortest path at all in that case.
O(V·E) is the price
Far slower than Dijkstra's O(E log V). Use it when weights can be negative - currency arbitrage detection, and the inner loop of Johnson's all-pairs algorithm.
Common pitfalls
- Relaxing out of unreached vertices. When dist[u] is infinity the edge must be skipped - in fixed-width integer languages, infinity plus a weight overflows into nonsense.
- Dropping the extra check pass. Without it, negative cycles go undetected and the returned distances look plausible while meaning nothing.
- Omitting the early exit. Correctness survives, but you always pay the full O(V·E) even on graphs that converge in two passes, as the default here does.
- Reporting distances despite a detected negative cycle. Any vertex reachable from the cycle has no shortest path at all - minus infinity, not a number.
- Confusing negative edges with negative cycles. Bellman-Ford handles negative edges fine; only a cycle whose weights sum below zero is fatal.
Where it is used
- Currency arbitrage: take logs of exchange rates and a negative cycle is a money pump.
- Distance-vector routing protocols like RIP, where each router iteratively relaxes routes learned from neighbours.
- The reweighting step inside Johnson's all-pairs algorithm for sparse graphs with negative edges.
- Interview problems that bound path length, like Cheapest Flights Within K Stops - k relaxation passes, by construction.
Frequently asked questions
What is the time and space complexity of Bellman-Ford?
Worst case O(V·E): up to V-1 passes, each relaxing all E edges. With the early exit it stops as soon as a pass changes nothing - best case O(E) when the first sweep already finds every shortest path. Space is O(V) for the distance table.
Why exactly V-1 passes?
Each pass guarantees correctness for shortest paths one edge longer than the last. A shortest path never repeats a vertex - repeating one would mean going around a cycle worth removing - so it has at most V-1 edges, and V-1 passes cover it.
How does Bellman-Ford detect a negative cycle?
Run one extra sweep after the V-1 passes. Any edge that still improves means some path kept getting cheaper past the simple-path limit, which is only possible by looping around a negative-weight cycle. The implementation here reports that edge and stops.
Should I use Bellman-Ford or Dijkstra?
Dijkstra whenever all weights are non-negative - O((V + E) log V) beats O(V·E) decisively. Bellman-Ford is for the cases Dijkstra cannot touch: negative edges, negative-cycle detection, or algorithms that need a fixed bound on path length.