cf.completefrontend
GRAPHS · ADVANCED

Floyd-Warshall

Find the cheapest path between every pair of nodes at once, by letting each node in turn act as a possible stop in the middle.

Time O(n³)Space O(n²)2 practice problemsStep-through picture

The idea

Sometimes you need the cheapest cost between every pair of nodes, not just from one start: a full table of travel times between all offices, for example. Floyd-Warshall builds that table with three nested loops.

It starts with a table dist where dist[i][j] is the cost of a direct edge from i to j, 0 when i === j, and Infinity otherwise. Then it considers each node mid in turn and asks, for every pair: is it cheaper to go from i to mid and then from mid to j?

After mid has gone through every node, the table holds the cheapest cost between every pair. It works with negative edges too, as long as there is no negative cycle. The cost is n³ steps, so it fits graphs of up to a few hundred nodes.

An everyday example

Adding layover cities one at a time

You have a table of direct flight prices between cities. First you allow layovers only in Paris: for every pair of cities, check whether flying through Paris is cheaper and update the table. Then you also allow layovers in Rome, using the already-updated table, so routes through both Paris and Rome are covered. After you have allowed every city, the table has the best price for any trip with any layovers.

How the example maps to the code
In the exampleIn the code
The table of pricesdist[i][j]
The city newly allowed as a layovermid
Flying from i to the layover, then on to jdist[i][mid] + dist[mid][j]
Updating the table with a cheaper routedist[i][j] = dist[i][mid] + dist[mid][j]

From the slow way to floyd-warshall

  1. Start with the obvious way: run a one-start algorithm from every node. Dijkstra from each of n starts costs O(n · e log n) but can't handle negative edges. Bellman-Ford from each start handles them, but on a dense graph that's about n⁴ steps: 100 million for just 100 nodes.
  2. Look at the cheapest paths in a different way: by which nodes they're allowed to stop at in the middle. With no middle stops allowed, the only paths are direct edges, and that's just the edge table. Now allow one more node, k, as a stop. A cheapest path from i to j either doesn't use k, so it's the answer we already had, or it goes through k once.
  3. If it goes through k, it splits into two halves, i to k and k to j, and each half only stops at nodes allowed before k. We already know the best cost of both halves. So allowing one new stop needs just one check per pair: is dist[i][k] + dist[k][j] smaller than dist[i][j]? That's a dynamic programming step, filling a table one allowed stop at a time.
  4. One more fact keeps the memory small. While k is the new stop, row k and column k can't improve, because going from i to k through k adds dist[k][k] = 0. So we can update a single n by n table in place instead of keeping a new table for every k. Three nested loops with mid on the outside: that is Floyd-Warshall.

How it works

  1. Make an n by n table dist: 0 on the diagonal, Infinity everywhere else.
  2. For each edge [from, to, weight], set dist[from][to] to the smaller of its current value and weight.
  3. For each mid from 0 to n - 1, go through every pair i, j.
  4. If dist[i][mid] + dist[mid][j] is less than dist[i][j], update dist[i][j].
  5. After the last mid, dist[i][j] is the cheapest cost from i to j, or Infinity if there's no path.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function floydWarshall(n, edges) {
  2. const dist = Array.from({ length: n }, (_, i) =>
  3. Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)),
  4. );
  5. for (const [from, to, weight] of edges) {
  6. dist[from][to] = Math.min(dist[from][to], weight);
  7. }
  8. for (let mid = 0; mid < n; mid++) {
  9. for (let i = 0; i < n; i++) {
  10. for (let j = 0; j < n; j++) {
  11. if (dist[i][mid] + dist[mid][j] < dist[i][j]) {
  12. dist[i][j] = dist[i][mid] + dist[mid][j];
  13. }
  14. }
  15. }
  16. }
  17. return dist;
  18. }

How fast it is

TimeO(n³)
Extra memoryO(n²)

Three nested loops each run n times. The table has one cell for every pair of nodes.

  • Best caseO(n³)

    Every input, even a graph with no edges: the three loops always run n × n × n checks.

  • Average caseO(n³)

    Every input; the number of updates changes, but the number of checks doesn't.

  • Worst caseO(n³)

    Every input. For n = 400 that's 64 million checks, which is about the practical limit.

Common mistakes

  • Putting the mid loop inside the i and j loops. The answer is then wrong for paths with several stops.
  • Forgetting dist[i][i] = 0, so a node seems unable to reach itself.
  • Overwriting a direct edge with a more expensive duplicate edge instead of keeping the minimum.
  • Using a large number like 1e9 instead of Infinity and then adding two of them together, which can look like a real path.

When to use it

Look for these clues in a problem:

  • The question needs the cheapest cost between many pairs, or every pair.
  • n is small, about 400 or less, so n³ steps are fine.
  • You need to know which nodes can reach which (a reachability table).
  • Edge costs may be negative, but there is no loop with a negative total.

Check yourself

Answer each one in your head first, then open it.

What goes wrong if mid is the innermost loop?

Each pair i, j is finished before the halves it needs have been improved, so paths with more than one stop are missed.

Why is it safe to update the table in place during a round?

The cells read in round mid, dist[i][mid] and dist[mid][j], can't change in that round, because improving them would add dist[mid][mid] = 0.

How many checks does it make for 50 nodes?

50 × 50 × 50 = 125,000, whatever the edges are.

In the trace, why did dist[2][1] become 10 only in the last round?

Its cheapest path is 2 → 3 → 0 → 1, which stops at node 3. Node 3 is only allowed as a stop in the last round, mid = 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule: after the outer loop finishes mid = k, dist[i][j] is the cheapest cost of a path from i to j whose middle stops are all among nodes 0 to k. Before the first round, no middle stops are allowed, and the table holds exactly the direct edges, with 0 on the diagonal.

Each round keeps the rule. A cheapest path that may stop at 0 to k either avoids k, and its cost is already in the table, or passes through k exactly once, since without negative loops repeating k never helps. Then its two halves only stop at 0 to k - 1, so their costs are dist[i][k] and dist[k][j]. Updating in place is safe, because during round k those two cells can't change: improving them would mean adding dist[k][k] = 0.

The loops always end after n³ checks. After the last round, every node is allowed as a stop, so the table holds the true cheapest costs. If there is a negative loop, some node on it ends with dist[i][i] < 0, because going around the loop from i back to i costs less than staying put.

Going deeper

3 more ideas

Why the order of the loops matters

After the outer loop finishes mid = k, dist[i][j] is the cheapest path from i to j that only stops at nodes 0 to k along the way. Moving to k + 1, a cheapest path either doesn't use node k + 1 (already correct) or goes i → k + 1 → j, and both halves only use stops up to k (also already correct). That's why mid must be the outer loop.

Cost and when to use something else

Three nested loops of n make n³ steps: 1 million for n = 100, 64 million for n = 400. If the graph is large but sparse and you need only a few starts, running Dijkstra from each start is cheaper. Floyd-Warshall wins on small, dense graphs and for its short code.

Negative cycles and reachability

If any dist[i][i] ends up below 0, node i is on a negative cycle. For a plain "can i reach j?" table, use booleans instead of numbers: reach[i][j] = reach[i][j] || (reach[i][mid] && reach[mid][j]).

Work it by hand

Every step in a table, with why

Four nodes with one negative edge and a duplicate edge. Every update the code makes is one row; the other 56 of the 64 checks change nothing.

n = 4, edges = [[0,1,5], [1,2,-2], [2,3,4], [3,0,1], [0,3,9], [3,1,8], [0,3,12]]

StepmidPair i → jOld dist[i][j]dist[i][mid] + dist[mid][j]What happensWhy
1-all edges--Load the tableRows start as [0, 5, ∞, 9], [∞, 0, -2, ∞], [∞, ∞, 0, 4], [1, 8, ∞, 0]. The two edges 0 → 3 cost 9 and 12, and Math.min keeps 9.
203 → 181 + 5 = 6Update to 6Allowing node 0 as a stop, 3 → 0 → 1 costs 6, cheaper than the direct edge of 8. No other pair improves through node 0.
310 → 2∞5 + (-2) = 3Update to 3Through node 1, node 0 reaches node 2 for the first time, helped by the negative edge.
413 → 2∞6 + (-2) = 4Update to 4This uses dist[3][1] = 6, found in the mid = 0 round. So the real path is 3 → 0 → 1 → 2, with two middle stops.
520 → 393 + 4 = 7Update to 7Going 0 → 1 → 2 → 3 costs 7, beating the direct edge of 9.
621 → 3∞-2 + 4 = 2Update to 2Node 1 reaches node 3 through node 2.
731 → 0∞2 + 1 = 3Update to 3Now node 3 is allowed too, so every path is possible. 1 → 2 → 3 → 0 costs 3.
832 → 0∞4 + 1 = 5Update to 5Node 2 reaches node 0 through node 3.
932 → 1∞4 + 6 = 10Update to 10dist[3][1] = 6 already includes the stop at node 0, so this is the path 2 → 3 → 0 → 1.

The final table is [0, 5, 3, 7], [3, 0, -2, 2], [5, 10, 0, 4], [1, 6, 4, 0]. The loops always make 4 × 4 × 4 = 64 checks; 8 of them updated a cell. Every dist[i][i] is still 0, so there is no negative loop.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Floyd-WarshallO(n³)O(n²)You need every pair, n is at most a few hundred, and you want short code that handles negative edges.
Dijkstra from every nodeO(n · e log n)O(n + e)The graph is large and sparse with no negative edges, or you only need a few starts.
Bellman-Ford from every nodeO(n² · e)O(n)Almost never for all pairs; it's slower than Floyd-Warshall on dense graphs and Johnson's on sparse ones.

Extra memory: O(n²): one n by n table, updated in place. Keeping a separate table for every mid would cost O(n³).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Floyd-Warshall and the other approaches, on a scale where each line up is 10 times more steps.
  • Floyd-Warshall, Bellman-Ford from every node O(n³)
  • Dijkstra from every node O(n · e log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Floyd-Warshall1,0001 billionmore than a quadrillion
Dijkstra from every node33210 million20 trillion
Bellman-Ford from every node1,0001 billionmore than a quadrillion

Inputs that need care

5 tricky inputs
No path from i to j
dist[i][j] stays Infinity. Infinity plus any number is still Infinity, so a missing half never wins a comparison.
Two edges for the same pair, like 0 → 3 costing 9 and 12
Math.min on line 6 keeps the cheaper one. Plain assignment would let the later, more expensive edge overwrite it.
A negative edge with no negative loop, like 1 → 2 costing -2
It works as is, as the trace shows.
A negative loop, or a negative self-loop like [2, 2, -1]
Some dist[i][i] ends below 0. Check the diagonal after the loops; costs between pairs that can use the loop are meaningless.
An undirected graph
Add each edge in both directions. A negative undirected edge is itself a negative loop.

Variations and follow-ups

Twists interviewers add

Rebuilding the paths

Keep a second table next, where next[i][j] starts as j for every edge. When dist[i][j] improves through mid, set next[i][j] = next[i][mid]. To list the path, start at i and keep jumping to next[current][j] until you reach j.

Widest paths

Replace + with Math.min and < with > to find, for every pair, the path whose narrowest edge is as wide as possible, such as the best bandwidth between servers. Start missing pairs at 0 instead of Infinity; the same mid argument applies.

Adding one edge later

If the table is already finished and a new edge u → v with cost w appears, you don't need to run it again. For every pair, try dist[i][u] + w + dist[v][j]. That's O(n²) per new edge.

Johnson's algorithm for big sparse graphs

Run Bellman-Ford once to give each node a potential, use it to turn every edge cost into a non-negative one, then run Dijkstra from every node. It finds all pairs in about O(n · e log n), which beats n³ when edges are few.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "between every pair", "for many queries of distance from a to b", or "which cities can reach which", with n up to about 400.
  • Explain the loop order out loud: "after round mid, the table is right for paths that only stop at nodes 0 to mid". That sentence answers the most common question, why mid must be the outer loop.
  • Test by hand a three-node chain where the only path from the first to the last needs a stop in the middle, and check that the cell fills in during the right round.
  • Expect "how would you detect a negative loop?". Answer: after the loops, any dist[i][i] < 0 means node i is on one.

Where frontend code uses it

The same idea in real UI code
  • Dashboards that show a full table of latencies or hop counts between every pair of services or regions.
  • Design tools that precompute which components can reach which through nested references, so a "used by" panel can answer any pair instantly.
  • Small games and puzzle apps that precompute distances between all key spots on a map once, then answer many queries during play.

Related algorithms