Cairn
algorithms · shortest paths · O(V · E)

↩ back to Shortest Paths

Bellman-Ford Algorithm

Dijkstra's algorithm is fast because it trusts a shortcut: once a node is popped from the priority queue, its distance is treated as final, forever. That shortcut relies entirely on every edge cost being non-negative — otherwise a cheaper route could still be hiding behind a node Dijkstra already gave up on. Bellman-Ford drops the shortcut entirely. Instead of finalizing anything early, it just relaxes every edge in the graph, over and over, exactly V - 1 times (V = number of nodes) — slower, but correct even with negative edges, and able to detect the one case where "shortest path" stops being a meaningful question at all: a negative-weight cycle.

Try it

Six stops in a shipping network, starting at Depot. Most routes cost something to run; one — South → East — is a subsidized rebate route that actually pays you 2 to use it, shown as -2. Press Step or Run to watch Bellman-Ford examine every edge, in the same fixed order, once per pass: the edge under examination gets a bold border, an edge that improves a distance turns orange and the node it points to flashes, and the strip below the graph shows the live shortest-known distance to every node at once (Bellman-Ford has no single "destination" — it computes distances to everywhere from the source in one run). Press Add rebate loop to add one more route, West → North, that also pays a rebate — 12 this time. That closes a loop (North → East → West → North) worth 3 + 2 - 12 = -7: a route planner could keep looping it forever, shaving the total cost lower every time. Step through again and watch the algorithm notice — instead of reporting some impressively low number, it correctly refuses to give North, East, West, or Market a finite shortest distance at all.

pass 0 / 5
Press Step or Run.

Why it works

The key fact: after Bellman-Ford has completed k full passes over every edge, every node's tracked distance is correct for the cheapest path to it that uses at most k edges — provable by induction on k, since pass k+1 relaxes every edge again, which is exactly what's needed to extend every k-edge shortest path by one more edge if that helps. A shortest simple path (one that doesn't repeat a node) in a graph with V nodes can never use more than V - 1 edges — repeating a node would mean a cycle, and cutting a cycle out of a path can only shorten it, never lengthen it, as long as the cycle doesn't have negative total weight. So V - 1 passes are always enough to find every true shortest path, and — unlike Dijkstra's greedy order — it doesn't matter what order the edges get relaxed in, or whether any of them are negative. Bellman-Ford trades away Dijkstra's early-finalization speed for a correctness argument that never needed non-negative weights in the first place.

That "as long as the cycle doesn't have negative total weight" caveat is also the detection mechanism. If a graph genuinely has no negative cycle reachable from the source, every distance is locked in by pass V - 1, and running the relaxation check one more time (a Vth pass) finds nothing left to improve. If something can still be improved after V - 1 passes, the only way that's possible is a cycle with negative total weight somewhere on a path back to it — otherwise the V - 1-edges argument above would already have caught it. That single extra pass is the whole detection story: relax every edge one more time, and treat any further improvement as proof a negative cycle exists upstream of whatever it just updated.

Reference implementation

Matches the demo above one for one — same edge order, same two-phase structure (relax V - 1 times, then one detection pass), just without the yield points the demo uses to show every intermediate comparison:

function bellmanFord(numNodes, edges, source) {
  // edges: [{ u, v, w }, ...] — directed, weight w (may be negative)
  const dist = new Array(numNodes).fill(Infinity);
  const pred = new Array(numNodes).fill(-1);
  dist[source] = 0;

  for (let pass = 0; pass < numNodes - 1; pass++) {
    for (const { u, v, w } of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pred[v] = u;
      }
    }
  }

  // Vth pass: anything that still relaxes is downstream of a negative cycle
  const inNegativeCycle = new Set();
  for (const { u, v, w } of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) inNegativeCycle.add(v);
  }

  if (inNegativeCycle.size > 0) {
    // flood-fill forward from the flagged nodes: everything reachable from
    // a negative cycle has an equally undefined "shortest" distance
    const queue = [...inNegativeCycle];
    while (queue.length) {
      const cur = queue.shift();
      for (const { u, v } of edges) {
        if (u === cur && !inNegativeCycle.has(v)) { inNegativeCycle.add(v); queue.push(v); }
      }
    }
    return { dist, pred, negativeCycle: true, affected: inNegativeCycle };
  }

  return { dist, pred, negativeCycle: false };
}

Pitfalls

It's much slower than Dijkstra when you don't need it. O(V · E) against Dijkstra's O((V + E) log V) — for a dense graph that's a real gap, and it isn't just a theoretical one: see Measuring against Dijkstra below for the actual measured wall-clock ratio, which grows into the tens of times slower well before a graph gets exotically large. Bellman-Ford is the right tool specifically when negative edges are possible (or need to be detected); reach for Dijkstra's algorithm whenever every edge is guaranteed non-negative, which is the common case.

The demo and reference implementation above don't include the standard early-exit optimization. If a full pass relaxes zero edges, every distance is already final — no later pass can ever change anything without a negative cycle, so a real implementation typically breaks out of the loop the moment a pass makes no changes, instead of always running the full V - 1 passes. Left out here for the same reason the priority queue on the Dijkstra's algorithm page is a plain array instead of a heap: the point of this page's demo is the algorithm's shape, and stepping through a pass that changes nothing is still worth seeing once, to make "it can't finalize anything early" a felt fact instead of an asserted one.

Only a negative cycle reachable from the source — and able to reach the node in question — actually breaks anything. A negative cycle sitting in some other disconnected part of the graph, or one the source can reach but that can't reach a given node in turn, leaves that node's shortest distance perfectly well-defined. The demo's own default graph makes half of this point already: the rebate edge South → East is negative but isn't part of a cycle, so it just makes that route cheaper, not undefined. Toggling the second rebate on closes an actual loop, and even then Depot and South keep finite distances — nothing loops back around to either of them, only forward from the cycle toward Market.

Measuring against Dijkstra

The two Big-O bounds above predict Bellman-Ford should lose ground as a graph gets denser — O(V · E) grows with every edge added, while Dijkstra's priority queue lets it ignore edges leaving an already-finalized node. To check that against real wall-clock time rather than just asserting it: the benchmark below runs this page's own bellmanFord reference implementation above, unchanged, against a Dijkstra adapted from Dijkstra's own reference implementation — same array-backed priority queue (linear-scan extract-min, no heap), generalized from that page's grid-specific version to the arbitrary edge list Bellman-Ford already takes, since the two pages' reference code uses different graph representations. Every run builds a fresh random directed graph with roughly half of all possible edges present (dense, matching the Pitfalls claim above) and non-negative integer weights, then checks both algorithms' resulting shortest-distance arrays against each other element by element before reporting any number — a mismatch would mean a bug in the benchmark code, not a real result, and gets reported as an internal error instead of a timing.

Pick a vertex count, then click Measure — it builds a fresh dense random directed graph (about half of all possible edges present, weights 1-20), runs both algorithms on it, cross-checks their answers against each other, and reports the median of 5 timed runs each.

Dozens of repeated runs against fresh random graphs (median of 5 timed runs each, as the widget above does) settled into a clear, size-dependent range, every one cross-checked against Dijkstra's own answer with zero mismatches: roughly 10×–14× slower at 100 vertices, widening to 25×–30× at 300 and 56×–69× at 600 — growing faster than the vertex count alone, consistent with the O(V · E) bound, since a fixed 50% density also means E itself is growing roughly with V². The 100-vertex size occasionally produced far lower outlier ratios (as low as 1.9× in testing) purely from this VM's shared-hardware scheduling noise swamping a signal that's only a couple of milliseconds wide at that scale — the same noise floor heap sort's own benchmark ran into at small sizes. 300 and 600 vertices were consistently far above that noise floor in testing, which is why 300 is the default. As with that benchmark, this is one VM's JavaScript engine, not a hardware-independent law — but the direction (the gap widens with density and size, it doesn't shrink or flip) is exactly what the asymptotic argument above predicts, and that held at every size tried.

Complexity

Time: O(V · E) — V - 1 passes (plus one detection pass), each relaxing every one of the E edges once. Space: O(V) for the distance array, the predecessor array, and (when a negative cycle is found) the affected-node set. See Measuring against Dijkstra above for how that bound translates into real wall-clock time.

All of the above is for one source. Need shortest paths between every pair of nodes at once — a full routing table, not just one source's distances? See the Floyd-Warshall algorithm, which reuses this exact graph and rebate-loop toggle so its demo is directly comparable to this one. Still need a single source, but want to skip re-examining edges nowhere near a distance that just changed? See the Shortest Path Faster Algorithm, which also reuses this exact graph and toggle. For a decision guide across all thirteen of this site's shortest-path entries, see Choosing a Shortest-Path Algorithm.