Bellman-Ford

The 10-second versionCopy Anchor Link

Relax every edge, over and over, V - 1 times. That is the whole algorithm. After V - 1 sweeps, no edge can still improve a distance, so dist holds the true shortest paths — even when some edges are negative, which is exactly where Dijkstra fell apart. Then run one final sweep: if it still improves anything, a reachable negative cycle exists and the shortest path is undefined (you could loop forever and keep getting cheaper). It is slower than Dijkstra but it survives the weights Dijkstra cannot.

Why this existedCopy Anchor Link

The problem is the same one Dijkstra solved — cheapest route — but with a twist that kept showing up in the real world: edges that can be negative. A negative weight is not exotic. It is a cost/credit, a discount, a currency exchange that can lose you money, a scheduling dependency that subtracts slack. The moment weights can go below zero, Dijkstra's "finalize and never revisit" proof evaporates.

This one has no single author. Four people circled the same idea in the span of four years:

• 1955 — Alfonso Shimbel, at the RAND Corporation, publishes a relaxation method for shortest paths — essentially the first statement of the technique.
• 1956 — Lester Ford states the relax-every-edge algorithm in his work on network flow.
• 1958 — Richard Bellman re-derives it as a dynamic-programming problem, which is why his name leads.
• 1959 — Edward F. Moore adds a queue-based refinement that only re-relaxes the nodes that actually changed.

Why it mattered: it was the first practical answer to "shortest paths with negative costs," and it turned out to be the exact engine behind distance-vector routing — the way a whole network of routers gossips its way to a routing table. Ford's and Moore's names are why it is often called Bellman-Ford-Moore, and Moore's queue version lives on in competitive programming as SPFA.

Inside the inventor's headCopy Anchor Link

Start with the exact counterexample that kills Dijkstra. Take S→A = 5, S→B = 2, and a single nasty edge B→A = -10. Dijkstra settles A at cost 5 because it looks cheapest at first — and then can never reconsider it. The true distance to A is 2 + (-10) = -8. Dijkstra returns 5 and confidently walks away wrong.

The pivot is beautifully lazy: if you cannot trust finalizing anything, then just don't finalize. Relax everything on every pass and let improvements ripple one hop further each round. Why V - 1 rounds? Because the shortest path that matters is simple — no repeated nodes — so it uses at most V - 1 edges. Each full pass pushes the known distances one edge further along the graph, so after V - 1 passes the furthest possible shortest path has been fully discovered. A V-th pass can only change something if there is a cycle you can go around for free profit — a negative cycle.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

1. Set dist[source] = 0 and every other dist to infinity.
2. Repeat V - 1 times: for every edge (u, v, w), if dist[u] + w is smaller than dist[v], relax it.
3. One extra pass over all edges: if any edge still relaxes, a reachable negative cycle exists.

The invariantCopy Anchor Link

After k full passes, dist[v] is the cost of the cheapest path from the source to v that uses at most k edges. This holds by induction: pass k can only improve a node by extending a path of at most k - 1 edges with one more edge. Since any shortest simple path has at most V - 1 edges, running V - 1 passes is exactly enough — and the V-th pass is a pure detector, not a fixer.

A worked traceCopy Anchor Link

Four nodes S, A, B, C, with directed edges S→A = 4, S→B = 1, B→A = -2, A→C = 5, B→C = 8. We relax them in that order, every pass:

Notice C only became reachable through A in pass 2, after A finally settled to -1 in pass 1. That is the whole reason you cannot stop early: information needs one pass per edge of distance to travel.

It in codeCopy Anchor Link

function bellmanFord(V, edges, src) {  const dist = new Array(V).fill(Infinity);  dist[src] = 0;  for (let pass = 0; pass < V - 1; pass++)    for (const { u, v, w } of edges)      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;  for (const { u, v, w } of edges)    if (dist[u] + w < dist[v]) return { dist, negativeCycle: true };  return { dist, negativeCycle: false };}

ComplexityCopy Anchor Link

One honest optimization: if a whole pass changes nothing, you can stop immediately — the distances have converged. That is what makes the best case O(E). (Moore's queue-based SPFA is the same idea taken further: only re-relax the nodes whose distance just changed, which is fast in practice but O(V · E) in the worst case.)

Where you meet it todayCopy Anchor Link

• Distance-vector routing (RIP). The Routing Information Protocol is Bellman-Ford wearing a network hat: each router keeps a vector of distances to every destination, neighbors exchange vectors, and repeated relaxation converges. The famous "count to infinity" problem and the split-horizon hack are direct consequences of the negative-cycle corner of this algorithm.
• Currency arbitrage. Give each exchange rate r the weight -log(r). A product of rates greater than 1 becomes a negative cycle — and Bellman-Ford finds it, which is how you detect risk-free profit across a set of currencies.
• Routing in general. BGP's path selection borrows the distance-vector idea, and any system that has to handle negative or "credit" costs reaches for Bellman-Ford before Dijkstra.
• Planning under uncertainty. Robotics and reinforcement learning states with negative rewards — where a "do nothing forever" loop would be pathological — depend on spotting that negative cycle.

The arbitrage trick is small enough to hold in your head: turn a product into a sum with a negative log, then look for the cycle that goes downhill.

// product of rates > 1  becomes  a negative cycleconst weight = (rateIj) => -Math.log(rateIj);

RecapCopy Anchor Link

• Bellman-Ford relaxes every edge, V - 1 times — no priorities, no finalizing, just brute repetition.
• It handles negative edge weights, which is the whole reason it exists next to Dijkstra.
• One extra pass that still relaxes proves a reachable negative cycle, so shortest paths are undefined.
• Cost: O(V · E) time and O(V) space — the price of generality.
• It is the algorithm underneath distance-vector routing (RIP) and currency-arbitrage detection.

Next up: Floyd-Warshall — stop doing one source at a time and answer every pair at once.