The Bellman–Ford Algorithm
Dijkstra's algorithm
is fast, but it makes one big assumption: no edge has a negative weight. Break
that assumption — a road that somehow refunds you time, a currency trade that gains value
— and Dijkstra can report the wrong answer, because once it finalises a vertex it never looks back.
Bellman–Ford — named after Richard Bellman
and Lester Ford — is the shortest-path algorithm that
copes with negative edges. It is
slower, but more patient: instead of greedily finalising the closest vertex, it just
relaxes every edge, over and over, and lets the distances settle.
Relaxation, repeated
The one operation is relaxing an edge u \to v of weight
w: if reaching u and then taking the edge is
cheaper than the best-known distance to v, update it.
\text{if } \operatorname{dist}(u) + w < \operatorname{dist}(v): \quad \operatorname{dist}(v) \leftarrow \operatorname{dist}(u) + w.
Bellman–Ford relaxes all the edges, then does it again, and again — exactly
V - 1 times for a graph of V vertices. Why
V - 1? Because a shortest path can visit at most
V vertices, so it has at most V - 1 edges;
one full pass is guaranteed to extend every shortest path by at least one more correct edge, so
after V - 1 passes they are all complete.
interface Edge { from: number; to: number; weight: number; }
// 5 vertices (0..4). Note the NEGATIVE edge 3 -> 1, which Dijkstra couldn't handle.
const V = 5;
const edges: Edge[] = [
{ from: 0, to: 1, weight: 6 },
{ from: 0, to: 2, weight: 7 },
{ from: 1, to: 3, weight: 5 },
{ from: 2, to: 3, weight: -3 },
{ from: 3, to: 1, weight: -2 },
{ from: 2, to: 4, weight: 9 },
{ from: 3, to: 4, weight: 7 },
];
const dist = Array(V).fill(Infinity);
dist[0] = 0; // start at vertex 0
// Relax every edge V-1 times.
for (let pass = 0; pass < V - 1; pass++) {
for (const e of edges) {
if (dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
console.log("shortest distances from 0:", dist.join(", "));
Vertex 1 ends up cheaper than its direct edge suggested, because the
route 0 \to 2 \to 3 \to 1 uses the negative edges — exactly the case
Dijkstra would get wrong.
Catching negative cycles
Bellman–Ford has a bonus power. After the V - 1 passes, do
one more. If any edge still relaxes — still finds a shorter distance —
then there is a negative cycle: a loop whose weights sum to less than zero. Around
such a loop you could keep going forever, getting "shorter" each time, so a shortest path simply
doesn't exist. That extra pass is how you detect it.
- Finds shortest paths from one source even with negative edge weights.
- Relax all edges V - 1 times; cost is O(VE).
- A V-th pass that still relaxes reveals a negative cycle.
Model currencies as vertices and exchange rates as edges. Take the negative logarithm of
each rate as the weight, and a path's total weight adds up the log-rates. A cycle of trades that
multiplies your money by more than 1 becomes a cycle whose weights sum
to less than zero — a negative cycle. So Bellman–Ford's negative-cycle detector is
literally an arbitrage detector: run it on the exchange table and it finds a
sequence of trades that turns money into more money.
-
Bellman–Ford is slower than Dijkstra — O(VE) versus
roughly O((V+E)\log V). Use it only when you actually have negative
edges; otherwise Dijkstra wins.
-
If a negative cycle is reachable from the source, "shortest path" is undefined
— you can loop forever getting cheaper. Bellman–Ford's job is to report that, not to
return a number.
-
You need exactly V - 1 passes — stopping early can leave some
distances not yet settled.