Introduction

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.

Watch the Matrix Improve

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">This graph has 5 nodes (A-E). The matrix below shows the best known distance between <b>every pair</b>. Click <b>Allow next intermediate</b> to switch on one node at a time as a permitted stopover — watch entries drop as new shortcuts appear.</p>
<div class="legend">Allowing through: <span id="allowed">none yet (direct edges only)</span></div>
<div id="matrix" class="matrix"></div>
<div class="status" id="status">Step 0 of 5 — only direct edges are known.</div>
<div class="btns">
  <button id="step" type="button">Allow next intermediate</button>
  <button id="all" type="button">Run all</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Floyd-Warshall: all-pairs shortest paths in O(V^3). The whole idea is a triple loop — for each intermediate node k, see if going i -> k -> j beats the best i -> j found so far:  dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]). We reveal it one k at a time so you can watch the matrix improve.
const NAMES = ['A','B','C','D','E'];
const N = 5, INF = Infinity;
// Directed weighted edges (u, v, w). No shortcuts pre-computed.
const EDGES = [
  [0,1,3],[0,2,8],[0,4,-4],
  [1,3,1],[1,4,7],
  [2,1,4],
  [3,0,2],[3,2,-5],
  [4,3,6]
];
let dist, k; // dist = current matrix, k = next intermediate to allow

function init(){
  dist = Array.from({length:N},(_,i)=>Array.from({length:N},(_,j)=> i===j?0:INF));
  EDGES.forEach(([u,v,w])=> dist[u][v] = Math.min(dist[u][v], w));
  k = 0;
}
function fmt(x){ return x===INF ? '∞' : String(x); }

function render(changed){
  changed = changed || new Set();
  const m = document.getElementById('matrix');
  m.style.gridTemplateColumns = 'repeat('+(N+1)+', auto)';
  m.innerHTML = '';
  const corner = document.createElement('div'); corner.className='cell corner'; m.appendChild(corner);
  for(let j=0;j<N;j++){ const h=document.createElement('div'); h.className='cell h'; h.textContent=NAMES[j]; m.appendChild(h); }
  for(let i=0;i<N;i++){
    const rh=document.createElement('div'); rh.className='cell h'; rh.textContent=NAMES[i]; m.appendChild(rh);
    for(let j=0;j<N;j++){
      const c=document.createElement('div');
      c.className='cell'+(i===j?' diag':'')+(changed.has(i+','+j)?' changed':'');
      c.textContent=fmt(dist[i][j]); m.appendChild(c);
    }
  }
  document.getElementById('allowed').textContent =
    k===0 ? 'none yet (direct edges only)' : NAMES.slice(0,k).join(', ');
  document.getElementById('step').disabled = k>=N;
  document.getElementById('all').disabled = k>=N;
}
function setStatus(t){ document.getElementById('status').textContent=t; }

// Relax ALL pairs through the single intermediate node k. This is one outer iteration of Floyd-Warshall.
function relaxThrough(kk){
  const changed = new Set();
  for(let i=0;i<N;i++) for(let j=0;j<N;j++){
    if(dist[i][kk]+dist[kk][j] < dist[i][j]){
      dist[i][j] = dist[i][kk]+dist[kk][j];
      changed.add(i+','+j);
    }
  }
  return changed;
}
function step(){
  if(k>=N) return;
  const changed = relaxThrough(k);
  k++;
  render(changed);
  setStatus(i18nFmt('Step %k% of %N% — allowed stops through %v%. %size% pair(s) got shorter.', { k: k, N: N, v: NAMES[k-1], size: changed.size }));
  if(k>=N) setStatus('Done — every entry is now the true shortest distance between that pair.');
}
function runAll(){ while(k<N) { relaxThrough(k); k++; } render(new Set()); setStatus('Done — full all-pairs shortest-path matrix in O(V³).'); }
function reset(){ init(); render(); setStatus(i18nFmt('Step 0 of %N% — only direct edges are known.', { N: N })); }

document.getElementById('step').addEventListener('click',step);
document.getElementById('all').addEventListener('click',runAll);
document.getElementById('reset').addEventListener('click',reset);
init(); render(); setStatus(i18nFmt('Step 0 of %N% — only direct edges are known.', { N: N }));
Result
Console

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.

The Real Complexity

How much work is hidden in those three loops?

  • Time: O(V3)O(V^{3}). For each of the V intermediate nodes, the algorithm scans all V2V^{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(V2)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).

Where It Matters

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.

Conclusion

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(V3)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/floyd-warshall/Content licensed under CC BY-NC 4.0.