Floyd-Warshall

A map app finds one route: from where you are to where you want to go. But sometimes you need all of them — the shortest distance between every pair of cities, every pair of routers, every pair of train stations, computed in advance so any later lookup is instant.

That is the all-pairs shortest path problem, and the Floyd-Warshall algorithm solves it with almost shocking economy: three nested loops over the nodes, and one line of arithmetic inside. Published by Robert Floyd in 1962 (building on Stephen Warshall's earlier work on transitive closure), it is one of the most elegant algorithms ever written.

The trick is a single, patient idea: let each node, one at a time, become a permitted stopover, and keep only the shortcuts it unlocks.

Below is a five-node network and its distance matrix: cell (row i, column j) holds the shortest distance currently known from i to j. At the start it knows only the direct edges — everything else is ∞.

<p class="hint">{{hint}}</p>
<div class="legend">{{allowing_through}} <span id="allowed">{{none_yet}}</span></div>
<div id="matrix" class="matrix"></div>
<div class="status" id="status">{{step_prefix}} 0 {{of_sep}} 5 — {{only_direct}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="all" type="button">{{btn_all}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.legend { font-size: .9rem; margin: 0 0 .6rem; color: #1d3557; }
.legend span { font-weight: 700; }
.matrix { display: inline-grid; gap: 3px; margin: .3rem 0 .6rem; }
.matrix .h { background: #1d3557; color: #fff; }
.matrix .corner { background: transparent; }
.cell { width: 50px; height: 40px; display: flex; align-items: center; justify-content: center;
        font: 700 15px ui-monospace, monospace; border-radius: 6px; background: #eef2f6; color: #1d3557; }
.cell.diag { background: #dbe3ea; color: #8a99a8; }
.cell.changed { background: #2a9d8f; color: #fff; transform: scale(1.06); transition: all .25s; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Allow next intermediate to switch on one node at a time as a permitted stopover. Each click runs the inner double loop: for every pair (i, j), it asks whether routing through the newly allowed node — dist[i][k] + dist[k][j] — beats the best route found so far. Highlighted cells just got shorter. After all five nodes are allowed, the matrix holds the true shortest distance between every pair — including paths with negative edges, which it handles correctly.

How much work is hidden in those three loops?

• Time: $O(V^{3})$. For each of the V intermediate nodes, the algorithm scans all $V^{2}$ pairs and does one comparison and one addition. With 1,000 nodes that is a billion operations — fast for a laptop, but it grows with the cube of the network size.
• Space: $O(V^{2})$. It stores a single distance matrix and updates it in place; no extra copy per step is needed.
• It is a solved, polynomial-time problem. Unlike many graph questions, this one is not hard. It sits firmly in P — there is no exponential blow-up, no open question about whether a fast method exists. (Compare that with the hardness explored in P vs NP.)
• Why it's correct. It is a clean piece of dynamic programming: after allowing nodes 1…k as stopovers, every entry is the shortest path using only those nodes as intermediates. Each new node can only ever improve the answer, never break it.

One subtlety: Floyd-Warshall happily handles negative edge weights, which simpler greedy methods cannot. It only fails if the graph contains a negative cycle — a loop you could ride forever to keep shrinking your distance — and it can even be used to detect one (a negative number on the diagonal).

Computing all shortest paths up front pays off whenever distances are queried again and again:

• Network routing: distance-vector protocols and traffic-engineering tools precompute pairwise costs across a network.
• Transitive closure: with the same triple loop you can compute reachability — who can reach whom — which is exactly Warshall's original algorithm.
• Graph metrics: the diameter of a network, average path length and centrality measures in social graphs all start from an all-pairs distance matrix.
• Operations and logistics: warehouse layout, circuit design and game-map pathfinding precompute distances between every pair of points.

When you only need one route from a single source, Dijkstra's algorithm is faster. But the moment you need the whole table — and especially with negative weights — Floyd-Warshall's three loops are hard to beat. It is a close cousin of other dynamic-programming gems like sequence alignment.

Floyd-Warshall is a quiet masterpiece. There is no clever data structure, no recursion to unwind — just three nested loops and the patient idea of letting one node at a time become a stopover. Out the other end comes the shortest distance between every pair of points in the network, in $O(V^{3})$ time.

It is a reminder that not every problem is a monster. Some, like this one, are completely solved — a fast, exact, beautiful method, settled since 1962. Once you have watched the matrix fill in, you have seen dynamic programming at its clearest, and met an algorithm worth keeping in your head for life.