Cairn
algorithms · shortest paths · O(V³)

↩ back to Shortest Paths

Floyd-Warshall Algorithm

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.

Try it

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.

step 0 / 37
Press Step or Run.

Why it works

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.

Reference implementation

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

Pitfalls

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.

Measuring the breakeven

The first Pitfall above says this page's O(V³) only pays off once "many or all pairs are actually needed" — true in direction, with no number behind "many." The benchmark below answers it directly: for a graph of a given size, how many sources' worth of shortest paths does a reader actually need before running Floyd-Warshall once costs less than running Dijkstra separately for each one? Builds a fresh random directed graph (same density/weight scheme as Bellman-Ford's own benchmark, non-negative weights so Dijkstra stays valid), times this page's own floydWarshall reference implementation above once, then times a Dijkstra adapted from Dijkstra's own reference implementation run from every single node in turn — cross-checking every one of those runs against Floyd-Warshall's own table before reporting anything, exactly as Bellman-Ford's own benchmark cross-checks against Dijkstra.

Pick a vertex count, then click Measure — it builds a fresh dense random directed graph (about half of all possible edges present, weights 1-20), times Floyd-Warshall once and Dijkstra from every single source, cross-checks every result against Floyd-Warshall's table, and reports how many sources' worth of Dijkstra runs it takes before their total time passes Floyd-Warshall's.

Repeated runs against fresh random graphs at this density (same density the widget defaults to), every one cross-checked against Floyd-Warshall's own table with zero mismatches, settled into a breakeven of roughly a quarter of all nodes at the smaller sizes, narrowing slightly as the graph grows: about 26%–28% of V at V=50, 23%–25% at V=100, and 20%–22% at V=200. So "many" turns out to mean "about a fifth to a quarter of all nodes need their own shortest-path tree" — well short of "most" or "all," and the threshold drops (not rises) as the graph gets bigger, because Floyd-Warshall's O(V³) and V runs of Dijkstra's O(V²) (dense graph, this page's own array-backed priority queue, no heap) both grow with V, but Floyd-Warshall's extra factor of V means its line crosses Dijkstra's cumulative total sooner, relative to V, every time the graph grows. As with Bellman-Ford's own benchmark, this is one VM's JavaScript engine's wall-clock time, not a hardware-independent law — but the direction (the breakeven fraction shrinks as V grows, it doesn't grow or flip) held at every size tried.

Complexity

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. See Measuring the breakeven above for how few sources it actually takes before that cost pays for itself.

For a decision guide across all thirteen of this site's shortest-path entries — including Johnson's Algorithm's textbook sparse-graph edge over this page's flat O(V³), and why its own array-backed reference code never actually reaches it — see Choosing a Shortest-Path Algorithm.