Bellman-Ford wastes most of its own effort: every one
of its V - 1 passes re-examines every edge in the graph, even edges nowhere near
a distance that just changed. SPFA replaces that fixed pass structure with a FIFO queue. Start with
only the source enqueued. Every time a node comes off the front of the queue, relax just its outgoing
edges — and enqueue a neighbor only when its distance actually improves, and only if it isn't already
waiting in the queue. Nothing gets examined that couldn't possibly still improve. The worst-case bound
is unchanged from Bellman-Ford — O(V · E), since an adversarial graph can still force
close to that much work — but on ordinary graphs only a small fraction of edges ever get re-checked,
which is where the name comes from. On this page's own six-node demo it converges in 7 dequeues and 9
relaxation checks total, against Bellman-Ford's fixed 45 checks over 5 full passes plus a 9-check
detection pass — 54 — on the identical graph.
The same six-stop shipping network as the Bellman-Ford
page, starting at Depot. Press Step or Run to
watch SPFA dequeue nodes from the queue strip below the graph and relax only that node's outgoing
edges: the node being processed gets a bold border, an edge under examination gets highlighted, an edge
that improves a distance turns orange and its target flashes, and — if that target wasn't already
waiting in line — it gets appended to the back of the queue. The distance strip shows the same live
shortest-known distances as the Bellman-Ford page. Press Add rebate loop to add the
identical West → North route paying -12, closing the same negative cycle. This time
watch the stats line: SPFA counts how many times each node gets enqueued, and the
instant one reaches 6 (this graph's node count), it stops and reports a negative cycle —
no waiting for a fixed extra pass. Check disable negative-cycle safeguard to see why
that count matters: with it off, the queue never empties on its own. This demo caps it at 20 dequeues
so the page doesn't hang; watch the distances just keep sliding further negative with no sign of
stopping.
A node's distance only ever gets smaller, never worse, and every improvement is exactly what triggers an enqueue. That's the same relaxation Bellman-Ford does — SPFA just skips the edges that plainly can't have anything to relax yet, because nothing near them has changed since they were last checked. The order nodes come off the queue doesn't matter for correctness, only for how much redundant work happens along the way; either way, the queue empties once nothing anywhere in the graph can improve any further.
The negative-cycle check reuses Bellman-Ford's own argument, just applied per node instead of via a
global pass count: a genuine shortest path is simple (it never repeats a node), so it has at most
V - 1 edges, and can trigger a given node's distance to improve — and so be enqueued — at
most that many times as a result. A node enqueued a Vth time means the chain of
relaxations that led there must have looped back through a node it had already passed through. The
only way looping back could still be an improvement is if going around that loop made the distance
smaller, not bigger — which is exactly what a negative-weight cycle is.
Matches the demo's own logic — adjacency list per node rather than a full edge scan, so only a dequeued node's own outgoing edges ever get examined:
function spfa(numNodes, adj, source) {
// adj[u] = [{ v, w }, ...] — outgoing edges from u
const dist = new Array(numNodes).fill(Infinity);
const pred = new Array(numNodes).fill(-1);
const inQueue = new Array(numNodes).fill(false);
const enqueueCount = new Array(numNodes).fill(0);
dist[source] = 0;
const queue = [source];
inQueue[source] = true;
enqueueCount[source] = 1;
while (queue.length) {
const u = queue.shift();
inQueue[u] = false;
for (const { v, w } of adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pred[v] = u;
if (!inQueue[v]) {
queue.push(v);
inQueue[v] = true;
enqueueCount[v]++;
if (enqueueCount[v] >= numNodes) {
return { dist, pred, negativeCycle: true, at: v };
}
}
}
}
}
return { dist, pred, negativeCycle: false };
}The worst case is exactly as bad as Bellman-Ford's. A queue doesn't change the asymptotic bound — it only helps on graphs where improvements don't cascade far. Adversarial graphs exist that force SPFA to re-examine close to as many edges as plain Bellman-Ford would, with extra bookkeeping overhead on top for maintaining the queue and the "already waiting" check. That's a known result from the graphs used to construct SPFA's own worst-case bound, not something this page's six-node demo is large enough to exhibit — it isn't adversarially constructed, so it shows the common-case speedup, not the worst case. This gap between "usually much faster" and "provably no better" is well documented and is the reason SPFA is treated as a practical shortcut for negative-edge graphs rather than a strict improvement on Bellman-Ford.
Unlike Dijkstra, a node can be dequeued and processed more than once — sometimes while its
distance is still far from final. The demo's own default graph (no rebate loop) shows this
directly: Market gets dequeued twice. The first time, its distance is still
13 — a real number, but not the eventual shortest distance of 6 — and since
Market has no outgoing edges, that first dequeue does nothing useful at all. Market only gets
re-enqueued once East finds a cheaper route to it later, and the second dequeue is
the one that matters. How many times a node gets revisited, and in what order, depends on the graph
and the order edges happen to be listed in — nothing here is predictable the way Dijkstra's
"finalize once popped" guarantee is.
Skip the enqueue-count check and a negative cycle doesn't just give a wrong answer — it
never terminates at all. Bellman-Ford always stops after a fixed V passes,
negative cycle or not, and only then checks whether anything's still improvable.
SPFA's queue has no such built-in stopping point: without the check, distances on a cycle keep
shrinking forever and the queue never empties on its own. Verified directly, independently of this
page's own demo: running the same graph with the rebate loop for 5,000 iterations without any
safeguard left the queue still non-empty and West's distance at -5,819 and still
falling, with no sign of convergence. The demo above caps the no-safeguard run at 20 dequeues for the
same reason — not because the algorithm would have stopped there on its own.
Time: O(V · E) worst case, same as Bellman-Ford — but frequently far
fewer relaxation checks in practice, since only edges leaving a node whose distance just improved ever
get re-examined. Space: O(V) for the distance array, predecessor array,
queue-membership flags, and per-node enqueue counters.
Need correctness guarantees that don't depend on how "typical" the graph is — or a fixed, predictable
amount of work every time? Bellman-Ford is the safer
default; reach for SPFA when the graph has negative edges and is large enough that Bellman-Ford's fixed
V - 1 passes are a real cost, not a theoretical one. For a decision guide across all eleven
of this site's shortest-path entries, see Choosing a Shortest-Path Algorithm.