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.
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.
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.
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 };
}
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.
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.
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.
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.