Bellman-Ford

Finding the cheapest route through a network is one of the oldest questions in computing. Map apps do it millions of times a second, and the famous fast answer is Dijkstra's algorithm — greedily expand outward, always grabbing the nearest unvisited node.

But Dijkstra rests on one quiet assumption: every edge costs something positive. The moment a road can give you value back — a currency trade that pays off, a discount, a refund — that greedy logic falls apart. A node Dijkstra "finalized" early can suddenly become cheaper through a negative detour it never considered.

The Bellman-Ford algorithm (Richard Bellman and Lester Ford, 1958) handles exactly this case. It is slower, but it is honest: it works with negative edge weights, and it can tell you when the question has no answer at all — when a negative cycle lets you loop forever and keep getting cheaper.

Here is a small directed graph. Each edge has a weight, and some are negative. Starting from node A, every node begins at distance infinity except A itself at 0. One round sweeps over all edges once and relaxes each: if going through an edge gives a shorter distance, update it.

<p class="hint">{{hint}}</p>
<div class="graphwrap">
  <svg id="graph" viewBox="0 0 360 240" aria-label="{{aria_graph}}"></svg>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <label class="chk"><input type="checkbox" id="cycle"> {{lbl_cycle}}</label>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.graphwrap { background: #f4f7fa; border: 1px solid #d8e1ea; border-radius: 10px; padding: 4px; }
svg { width: 100%; height: auto; display: block; }
.edge { stroke: #8aa0b4; stroke-width: 2; }
.edge.neg { stroke: #e63946; }
.edge.relaxed { stroke: #0a7d33; stroke-width: 3; }
.elabel { font: 600 12px ui-monospace, monospace; fill: #1d3557; }
.elabel.neg { fill: #c92f3c; }
.node circle { fill: #fff; stroke: #1d3557; stroke-width: 2.5; }
.node.src circle { fill: #1d3557; }
.node text.name { font: 700 14px system-ui; fill: #1d3557; text-anchor: middle; }
.node.src text.name { fill: #fff; }
.node text.dist { font: 700 12px ui-monospace, monospace; fill: #0a7d33; text-anchor: middle; }
.node.updated circle { stroke: #0a7d33; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.chk { font-size: .88rem; color: #333; display: flex; align-items: center; gap: .3rem; }

// Code not found

Press Run one round and watch the distances drop. The magic guarantee: after at most V-1 rounds (here V is the number of nodes), every shortest distance has settled. Then run one extra round — if anything still improves, the graph contains a negative cycle and no shortest path exists. Toggle the negative cycle on and see Bellman-Ford catch it.

How hard is single-source shortest path with negative weights? Solved — and efficiently so.

• Why V-1 rounds suffice. Any shortest path visits each node at most once, so it has at most V-1 edges. Each round of relaxation guarantees that one more edge of every shortest path is locked in. After V-1 rounds, the longest possible shortest path is fully settled.
• Running time is $O(V \cdot E)$. Every round touches all E edges, and there are V-1 rounds. That is polynomial — firmly in P — though slower than Dijkstra's $O(E \log V)$ on graphs with only positive weights.
• Negative-cycle detection is free. Run one round beyond V-1. If any distance still drops, a negative cycle is reachable, and "shortest path" becomes meaningless — you could loop forever to get arbitrarily cheap.
• It's a dynamic program. Bellman-Ford is the textbook example of building an answer from smaller subanswers ("shortest path using at most k edges"), the same idea behind countless optimization algorithms.

The takeaway: this is not an open or intractable problem. Bellman-Ford is a complete, correct, polynomial answer. Its only price is being slower than the greedy approach — the cost of refusing to assume the world only ever charges you.

Whenever costs can be negative — or when nodes must compute paths from only local information — Bellman-Ford shows up:

• Internet routing. The classic Routing Information Protocol (RIP) is a distributed Bellman-Ford: each router knows only its neighbors' distances and repeatedly relaxes, exactly like one round of the algorithm spread across the network.
• Currency arbitrage. Model exchange rates as edges with weights -log(rate). A negative cycle is then a sequence of trades that returns more money than you started with — and Bellman-Ford's extra round detects it.
• Constraint systems. "x must be at least k more than y" inequalities map to a graph; a negative cycle means the constraints are contradictory.
• A subroutine for the big leagues. Johnson's algorithm uses one Bellman-Ford pass to reweight a graph so that fast Dijkstra runs can finish an all-pairs shortest-path computation.

The same relaxation that crawls a tiny demo graph also keeps packets flowing and flags impossible markets. Compare it with the broader question of P vs NP: shortest path, even with negatives, lands squarely on the easy side.

Bellman-Ford is a lesson in patience. Where Dijkstra races ahead and commits, Bellman-Ford simply relaxes every edge, over and over, trusting that V-1 sweeps are enough to let the truth settle. That patience is what lets it survive negative roads — and what lets it recognize a negative cycle, the rare case where no shortest path exists at all.

It will never be the fastest router on a positive-weight map. But it answers a strictly harder question, gives a definite "no answer" when there genuinely is none, and does it all in polynomial time. In a field haunted by problems we cannot solve efficiently, Bellman-Ford is a quiet reminder of how much a simple, repeated idea can accomplish.