Floyd-Warshall

Update an all-pairs distance matrix by allowing one additional intermediate vertex per round.

Core idea

Dynamic programming expands the set of allowed intermediate vertices. For each pivot k, every ordered pair i and j asks whether traveling through k beats its current best distance.

Read the visualization

The highlighted pivot row and column provide the two candidate legs. The active matrix cell either accepts their sum or keeps its previous distance.

	A	B	C	D
A	0	3	6	∞
B	∞	0	2	4
C	∞	∞	0	1
D	5	∞	∞	0

Initialize direct edge distances, zero diagonals, and infinity for unknown routes.

1function floyd(adj: number[][], n: number): number[][] {
const dist = adj.map((row) => [...row]);
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] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}
return dist;
13}

intermediate k-

already update0

1 / 19

Complexity and tradeoffs

Time: O(V^3). Space: O(V^2). Handles negative edges but not negative cycles; the matrix is practical for dense, moderate graphs.

Invariant: After pivot k, every matrix entry is the shortest path whose intermediate vertices come only from the processed pivot set.

Where it fits

Floyd-Warshall is concise for dense graphs, transitive closure, and moderate all-pairs queries. Sparse large graphs usually favor repeated single-source algorithms.

Algorithm Visualizer

Floyd-Warshall

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits