Floyd-Warshall answers "shortest path between every
pair" correctly even with negative edges, but always pays O(V³), whether the graph is
dense or barely connected. Running Dijkstra's algorithm once
from every node would be cheaper on a sparse graph — but Dijkstra's speed depends on trusting that
once a node is finalized, nothing negative can ever undercut it, so it silently gives wrong answers
the moment an edge is negative. Johnson's algorithm gets both: one
Bellman-Ford pass computes a per-node number, a
potential, that reweights every edge into something non-negative without changing
which path is shortest — and then it's safe to run Dijkstra from every node after all.
Same six-stop shipping network as the Bellman-Ford and
Floyd-Warshall pages — same nodes, same edges, same
subsidized South → East rebate route (-2) — so all three are directly
comparable. Press Step or Run to watch the three phases in order.
First, a Bellman-Ford pass from an imaginary extra node connected to everywhere by a free edge computes
a potential for each real node — the strip below the graph tracks it live. Second, once potentials
converge, every edge is reweighted (w' = w + h(u) - h(v)) and the graph's edge
labels update to show it — watch every reweighted number land at zero or above, even the rebate route.
Third, Dijkstra runs once per source on the reweighted graph, ordinary and unmodified, filling one row
of the same all-pairs table Floyd-Warshall builds — converted back to real distances as each row
completes. Press Add rebate loop to add the same second rebate route
(West → North, -12) the other two pages use, closing an actual negative
cycle: watch the potentials phase itself catch it and abort before Dijkstra ever runs, since a
reweighting built on a still-changing potential can't be trusted to keep every edge non-negative.
The reweighting rule is w'(u, v) = w(u, v) + h(u) - h(v), where h(v) is
the shortest distance from an imaginary source q — wired to every real node by a free,
zero-weight edge — to v, using the real edges. Take any path
v₀ → v₁ → ... → vₖ and sum its reweighted edges:
Σ (w(vᵢ, vᵢ₊₁) + h(vᵢ) - h(vᵢ₊₁)). Every interior h term appears once
added and once subtracted and cancels — a telescoping sum — leaving
Σ w(vᵢ, vᵢ₊₁) + h(v₀) - h(vₖ): the path's real cost, plus a constant that depends only on
its two endpoints, never on which path was taken between them. So the reweighted graph ranks paths
between any fixed pair of nodes in exactly the same order the real graph does — whichever path
Dijkstra finds cheapest after reweighting was already cheapest before it, and converting back is just
undoing that same constant shift: real_dist(u, v) = reweighted_dist(u, v) - h(u) + h(v).
That still leaves one thing to prove: that reweighting actually produces non-negative edges. This
is where h being a genuine shortest-distance value does the work. Bellman-Ford's own
relaxation invariant, once converged, guarantees h(v) ≤ h(u) + w(u, v) for every edge —
otherwise that edge would still have something left to relax. Rearranged, that's exactly
w(u, v) + h(u) - h(v) ≥ 0: every reweighted edge, guaranteed. The one requirement
underneath all of it is that h converges to real numbers for every node in the first
place — which needs no negative cycle anywhere reachable from q. Since q
has a direct edge to every node, "reachable from q" means the whole graph, so the
condition is just: no negative cycle at all. That's precisely what Bellman-Ford's extra detection pass
already checks, for free, as part of computing h in the first place.
Matches the demo's three phases exactly — reweight, then plain Dijkstra once per source, then
convert back — just without the yield points the demo uses to animate one phase at a
time. Uses the same array-scan Dijkstra as the
Dijkstra's algorithm page, run once per node:
function johnsonsAlgorithm(numNodes, edges) {
// edges: [{ u, v, w }, ...] — directed, weight w (may be negative)
// phase 1: Bellman-Ford from a virtual source with a free edge to every node
const h = new Array(numNodes).fill(0); // dist(q, v) starts at 0 via the free edge
for (let pass = 0; pass < numNodes; pass++) {
let changed = false;
for (const { u, v, w } of edges) {
if (h[u] + w < h[v]) { h[v] = h[u] + w; changed = true; }
}
if (pass === numNodes - 1 && changed) return { negativeCycle: true };
if (!changed) break;
}
// phase 2: reweight every edge so every weight is >= 0
const reweighted = edges.map(({ u, v, w }) => ({ u, v, w: w + h[u] - h[v] }));
const adj = Array.from({ length: numNodes }, () => []);
for (const { u, v, w } of reweighted) adj[u].push({ v, w });
// phase 3: plain Dijkstra from every node on the reweighted graph, converted back
const allDist = [];
for (let src = 0; src < numNodes; src++) {
const dist = new Array(numNodes).fill(Infinity);
const visited = new Array(numNodes).fill(false);
dist[src] = 0;
for (let iter = 0; iter < numNodes; iter++) {
let u = -1, best = Infinity;
for (let i = 0; i < numNodes; i++) if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; }
if (u === -1) break;
visited[u] = true;
for (const { v, w } of adj[u]) {
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
}
}
allDist.push(dist.map((d, v) => (d === Infinity ? Infinity : d - h[src] + h[v])));
}
return { dist: allDist, negativeCycle: false };
}The virtual source has to be genuinely virtual, not a stand-in real node. Picking
some existing node and running Bellman-Ford from it instead looks like a shortcut, but any node that
can't reach some other node leaves that node's h value at Infinity, and the
reweighting formula breaks for every edge running into it. The virtual source's whole job is
guaranteeing a finite, well-defined h(v) for every node whenever the graph has
no negative cycle — a zero-weight edge straight to each one makes that automatic, and no real node in
the graph can promise the same.
Negative-cycle detection happens exactly once, in phase 1 — and Dijkstra must never run at
all if it fires. The proof above that reweighted edges are non-negative leans entirely on
h being a converged, correct shortest-distance value; a negative cycle means Bellman-Ford
never converges; the demo's own detection pass shows why by never letting the potentials strip settle
(toggle the rebate loop above and watch North's potential keep dropping, pass after pass, exactly the
unbounded behavior a cycle worth 3 + 2 - 12 = -7 per lap predicts). Feeding a still-wrong
h into the reweighting step would hand Dijkstra a graph that isn't actually guaranteed
non-negative, silently reintroducing the exact bug Johnson's algorithm exists to avoid.
The complexity win is real, but only on sparse graphs. Phase 1 costs
O(V · E); phase 3 runs Dijkstra V times, O(V · (V + E) log V)
with a binary heap (a Fibonacci heap tightens this to the more commonly cited
O(V² log V + V · E)). Either way, on a dense graph where E is close to
V², that's no better than Floyd-Warshall's flat O(V³) — sometimes worse, once
the per-edge and per-heap-operation constants are counted. The advantage shows up specifically when
E is much smaller than V²: a road network or a sparse dependency graph, not a
near-complete one.
Time: O(V · E) for the Bellman-Ford reweighting pass, plus
V runs of Dijkstra at O((V + E) log V) each with a binary heap —
O(V² log V + V · E log V) altogether, or the tighter textbook figure
O(V² log V + V · E) with a Fibonacci
heap. The array-backed Dijkstra in the demo and
reference code above turns each of those V runs into O(V² + E) instead,
same trade-off the Dijkstra's algorithm page makes for the same
reason. Space: O(V²) for the final all-pairs table, plus
O(V + E) for the potentials and the reweighted adjacency list.
For a decision guide across all eleven of this site's shortest-path entries — including exactly when this page's sparse-graph advantage over Floyd-Warshall actually pays off — see Choosing a Shortest-Path Algorithm.