Introduction

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.

Relax the Edges

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">Distances start at ∞ for every node except the source <b>A</b> (=0). Each <b>round</b> relaxes all edges once. After at most <b>V-1</b> rounds the shortest distances settle; one extra round that still improves means a <b>negative cycle</b>.</p>
<div class="graphwrap">
  <svg id="graph" viewBox="0 0 360 240" aria-label="graph"></svg>
</div>
<div class="status" id="status">Round 0 of 4. Press "Run one round".</div>
<div class="btns">
  <button id="step" type="button">Run one round</button>
  <button id="auto" type="button">Run all rounds</button>
  <label class="chk"><input type="checkbox" id="cycle"> Add a negative cycle</label>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bellman-Ford: relax EVERY edge V-1 times; one extra improving round => negative cycle.
// Nodes laid out on the SVG. Edges include one negative weight; a checkbox swaps in a
// negative cycle (B->C->B summing < 0) so the extra round keeps improving forever.
const POS = { A:[40,120], B:[140,50], C:[140,190], D:[250,50], E:[320,120] };
const NODES = Object.keys(POS);
// base graph (has a negative edge but NO negative cycle)
const BASE = [
  ['A','B',6],['A','C',7],['B','C',8],['B','D',5],['B','E',-4],
  ['C','D',-3],['C','E',9],['D','B',-2],['E','D',7]
];
// negative-cycle variant: D->B = -8 makes B->D->B = 5 + -8 = -3 < 0
const CYCLE = BASE.map(e => (e[0]==='D'&&e[1]==='B') ? ['D','B',-8] : e.slice());

let edges = BASE, dist = {}, round = 0, done = false;
const V = NODES.length; // 5  => V-1 = 4 rounds

function resetState(){
  edges = document.getElementById('cycle').checked ? CYCLE : BASE;
  dist = {}; NODES.forEach(n => dist[n] = Infinity); dist['A'] = 0;
  round = 0; done = false;
  draw([]); setStatus(i18nFmt('Round 0 of %v%. Press "Run one round".', { v: V-1 }),'');
}
function setStatus(t,c){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+c; }
const fmt = d => d===Infinity ? '∞' : String(d);

// One round: relax all edges once. Returns {improved, relaxedEdges, updatedNodes}.
function oneRound(){
  let improved=false; const relaxed=[]; const upd=new Set();
  edges.forEach(([u,v,w],i)=>{
    if(dist[u]!==Infinity && dist[u]+w < dist[v]){
      dist[v]=dist[u]+w; improved=true; relaxed.push(i); upd.add(v);
    }
  });
  return {improved, relaxed, upd};
}

function step(){
  if(done) return;
  if(round < V-1){
    const r = oneRound(); round++;
    draw(r.relaxed, r.upd);
    if(round < V-1) setStatus(i18nFmt('Round 0 of %round% of %v% done. %v2%', { round: round, v: V-1, v2: r.improved ? 'distances dropped.' : 'nothing changed.' }), '');
    else setStatus(i18nFmt('Round 0 of %round% of %v% done. Now run one extra round to check for a negative cycle.', { round: round, v: V-1 }), 'ok');
  } else {
    // extra verification round
    const r = oneRound();
    draw(r.relaxed, r.upd);
    if(r.improved){ done=true; setStatus('✗ Extra round still improved a distance → NEGATIVE CYCLE. No shortest path exists.','bad'); }
    else { done=true; setStatus('✓ Extra round changed nothing → distances are final and correct.','ok'); }
  }
}
function runAll(){ resetState(); let guard=0; while(!done && guard++<20) step(); }

function draw(relaxedIdx, upd){
  const svg = document.getElementById('graph'); svg.innerHTML='';
  const NS='http://www.w3.org/2000/svg';
  // edges
  edges.forEach(([u,v,w],i)=>{
    const [x1,y1]=POS[u],[x2,y2]=POS[v];
    // shorten to node edge (r=16)
    const dx=x2-x1, dy=y2-y1, L=Math.hypot(dx,dy), ux=dx/L, uy=dy/L;
    const sx=x1+ux*16, sy=y1+uy*16, ex=x2-ux*18, ey=y2-uy*18;
    const ln=document.createElementNS(NS,'line');
    ln.setAttribute('x1',sx);ln.setAttribute('y1',sy);ln.setAttribute('x2',ex);ln.setAttribute('y2',ey);
    let cls='edge'+(w<0?' neg':'')+((relaxedIdx||[]).includes(i)?' relaxed':'');
    ln.setAttribute('class',cls); ln.setAttribute('marker-end','url(#arr)');
    svg.appendChild(ln);
    const tx=(sx+ex)/2 + (uy*9), ty=(sy+ey)/2 - (ux*9);
    const t=document.createElementNS(NS,'text');
    t.setAttribute('x',tx);t.setAttribute('y',ty);t.setAttribute('class','elabel'+(w<0?' neg':''));
    t.textContent=w; svg.appendChild(t);
  });
  // arrow marker
  const defs=document.createElementNS(NS,'defs');
  defs.innerHTML='<marker id="arr" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto"><path d="M0 0 L6 3 L0 6 z" fill="#8aa0b4"/></marker>';
  svg.appendChild(defs);
  // nodes
  NODES.forEach(n=>{
    const [x,y]=POS[n];
    const g=document.createElementNS(NS,'g');
    g.setAttribute('class','node'+(n==='A'?' src':'')+((upd&&upd.has(n))?' updated':''));
    const c=document.createElementNS(NS,'circle'); c.setAttribute('cx',x);c.setAttribute('cy',y);c.setAttribute('r',16); g.appendChild(c);
    const nm=document.createElementNS(NS,'text'); nm.setAttribute('x',x);nm.setAttribute('y',y-1);nm.setAttribute('class','name'); nm.textContent=n; g.appendChild(nm);
    const ds=document.createElementNS(NS,'text'); ds.setAttribute('x',x);ds.setAttribute('y',y+27);ds.setAttribute('class','dist'); ds.textContent=fmt(dist[n]); g.appendChild(ds);
    svg.appendChild(g);
  });
}

document.getElementById('step').addEventListener('click',step);
document.getElementById('auto').addEventListener('click',runAll);
document.getElementById('reset').addEventListener('click',resetState);
document.getElementById('cycle').addEventListener('change',resetState);
resetState();
Result
Console

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.

The Real Complexity

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⋅E)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(Elog⁡V)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bellman-ford/Content licensed under CC BY-NC 4.0.