Floyd-Warshall

Find shortest paths between all pairs of nodes.

How it works

Floyd-Warshall solves the all-pairs shortest path problem: for every pair of vertices (i, j) it finds the minimum-cost path, considering any sequence of intermediate vertices. The algorithm builds the solution incrementally using dynamic programming.

The key insight is a 3D recurrence: `dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])`. In words: the cheapest path from i to j that may only route through vertices {0..k} is either the cheapest path that avoids k entirely, or the concatenation of the cheapest i→k path and the cheapest k→j path. Because each row only depends on the previous one, the matrix can be updated in-place, reducing space from O(V³) to O(V²).

The triple nested loop gives O(V³) time — much slower than running Dijkstra from every source (O(V(V+E) log V) for sparse graphs), but Floyd-Warshall handles negative edge weights (though not negative cycles), requires no priority queue, and is trivial to implement. A post-pass checking whether any diagonal entry dist[i][i] < 0 detects negative cycles.

Complexity

Best case

O(V³)

Average case

O(V³)

Worst case

O(V³)

Space

O(V²)

Visualizer

Generating steps…

Where it's used in the real world

Network routing tables

Pre-computing full mesh reachability and latency matrices

Small autonomous systems with dense topologies use Floyd-Warshall to build complete distance tables offline; the resulting matrix is then used to answer any-pair shortest-path queries in O(1) at runtime.

Game AI / navigation meshes

Pre-baking shortest paths between all waypoints in a level

Game maps often have a fixed set of waypoints. Running Floyd-Warshall once at load time stores the full path matrix so that any NPC can look up the next move toward any target in constant time during gameplay.

Transitive closure (reachability)

Determining which nodes can reach which others in a directed graph

Setting all edge weights to 1 and treating null (∞) as unreachable gives Boolean reachability — the Warshall variant. Used in compilers (type hierarchy checks), databases (foreign-key closure), and dependency solvers.

Implementation

function floydWarshall(n: number, edges: {from:number; to:number; weight:number}[]): (number|null)[][] {
  const INF = Infinity;
  const dist: number[][] = Array.from({length: n}, (_, i) =>
    Array.from({length: n}, (_, j) => (i === j ? 0 : INF))
  );

  for (const {from, to, weight} of edges) {
    dist[from][to] = weight;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] === INF || dist[k][j] === INF) continue;
        const via = dist[i][k] + dist[k][j];
        if (via < dist[i][j]) dist[i][j] = via;
      }
    }
  }

  // Return null for unreachable pairs
  return dist.map(row => row.map(v => v === INF ? null : v));
}

Related algorithms

Bellman-FordLive

Single-source shortest paths that handles negative edge weights.

O(VE)

Dijkstra's AlgorithmLive

Find shortest paths from a source node using a priority queue.

O((V+E) log V)