Dijkstra's algorithm and
Bellman-Ford both answer the same question — cheapest path
from one source to everywhere — just under different assumptions about the edges. Floyd-Warshall
answers a different question entirely: cheapest path between every pair of nodes, all at once. It
does this without touching a queue or a source node at all. Instead it asks, for every pair
(i, j), one question repeatedly: "is routing through node k ever cheaper than
what I already know?" — for every possible intermediate k, in order. By the time every
k has had a turn, every shortest path has been considered from every angle, because any real
shortest path's intermediate stops are just some subset of {0, 1, ..., V-1}, and the loop tries
all of them.
Same six-stop shipping network as the Bellman-Ford page —
same nodes, same edges, same subsidized South → East rebate route (-2) — so
the two demos are directly comparable. Instead of one strip of distances from a single source,
Floyd-Warshall builds a full 6×6 table: every row is a source, every column is a destination. Press
Step or Run to watch it work through the graph: the node currently acting
as the "through" stop is highlighted, one row of the table is recomputed against it, and any cell that just
improved flashes. Press Add rebate loop to add the same second rebate route
(West → North, -12) Bellman-Ford's demo uses, closing an actual negative
cycle — and watch how Floyd-Warshall notices: not with a "some nodes have no defined distance" message, but
with the table's own diagonal going negative for the nodes sitting on the cycle.
The invariant driving the whole thing: after the outer loop has considered intermediate nodes
0 through k, dist[i][j] holds the cheapest path from i
to j that only passes through intermediate nodes in that range — a path is allowed to use node
k itself as a stop, or not, but nothing numbered higher than k yet. That's exactly
what one round of the update rule enforces: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
either keeps the best path found using nodes 0..k-1 (the "don't use k" case) or
routes through k once, glued from two paths — i to k and
k to j — that are themselves already correct for nodes 0..k-1 by the
same inductive assumption one level down. Neither of those two sub-paths needs to revisit k
itself: a real shortest path never benefits from passing through the same node twice. Run k
from 0 up to V-1 and every intermediate node has had its turn — the final table is
correct for paths using any node at all, which is every real path there is.
Because dist is one shared V × V table updated in place, no auxiliary
per-source bookkeeping is needed the way running Dijkstra's algorithm
or Bellman-Ford once per source would require. That's the whole
trade this algorithm makes: three nested loops, O(V³), in exchange for every pair's answer at
once instead of one source's.
Matches the demo's update rule and loop order exactly, just without the per-row
yield points the demo uses to animate one row of one k at a time:
function floydWarshall(numNodes, edges) {
// edges: [{ u, v, w }, ...] — directed, weight w (may be negative)
const dist = Array.from({ length: numNodes }, () => new Array(numNodes).fill(Infinity));
for (let i = 0; i < numNodes; i++) dist[i][i] = 0;
for (const { u, v, w } of edges) {
if (w < dist[u][v]) dist[u][v] = w; // keep the cheaper of any parallel edges
}
for (let k = 0; k < numNodes; k++) {
for (let i = 0; i < numNodes; i++) {
if (dist[i][k] === Infinity) continue;
for (let j = 0; j < numNodes; j++) {
if (dist[k][j] === Infinity) continue;
const through = dist[i][k] + dist[k][j];
if (through < dist[i][j]) dist[i][j] = through;
}
}
}
// a negative diagonal entry means node i has a negative-cost path back to itself —
// proof a negative cycle passes through it
const negativeCycleNodes = [];
for (let i = 0; i < numNodes; i++) {
if (dist[i][i] < 0) negativeCycleNodes.push(i);
}
return { dist, negativeCycleNodes };
}O(V³) is a real cost, not just a bigger constant. For a graph where you
only ever need paths from one source, running Dijkstra's algorithm
(O((V + E) log V)) or Bellman-Ford
(O(V · E)) once is cheaper than computing every pair here and throwing away everything but one
row. Floyd-Warshall earns its keep specifically when many or all pairs are actually needed — a routing table
for a whole network, say — not as a general-purpose single-source replacement.
Negative-cycle detection here is a genuinely different, weaker-sounding check than
Bellman-Ford's, and it's worth understanding exactly what it does and doesn't tell you.
Bellman-Ford's page flood-fills forward from every node its
extra detection pass still improves, flagging the full set of nodes reachable from a negative cycle — in
that demo's own graph, toggling the rebate loop flags North, East, West, and Market, since Market
is downstream of the cycle even though it isn't part of it. Floyd-Warshall's diagonal check only catches a
node i where dist[i][i] itself went negative — meaning i has a
negative-cost path back to itself, i.e. i sits on the cycle. Toggle the same rebate
loop in the demo above and only North, East, and West go negative on the diagonal; Market's diagonal entry
stays exactly 0, even though its distance from North is no longer a meaningful number. The
diagonal check proves a negative cycle exists and names who's on it — it does not, by itself, tell you which
other cells in the table became meaningless because of it.
Parallel edges need an explicit tie-break before the loop starts. If the input has more
than one edge between the same ordered pair of nodes, only the cheapest should seed dist[u][v]
— the reference implementation above does this with a plain comparison during initialization
(if (w < dist[u][v])) rather than just overwriting with whichever edge came last, which would
silently keep an arbitrary one instead of the correct one.
Time: O(V³) — three nested loops over every node, independent of how many
edges actually exist (a dense graph and a sparse one with the same node count cost the same). Space:
O(V²) for the distance table — unavoidable, since the whole point is producing an answer for every
pair.
For a decision guide across all eleven of this site's shortest-path entries — including when
Johnson's Algorithm beats this page's flat
O(V³) on a sparse graph — see Choosing a Shortest-Path Algorithm.