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. 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.
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.
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 eleven of this site's shortest-path entries, see Choosing a Shortest-Path Algorithm.