Floyd-Warshall

All-pairs shortest paths via a distance matrix. For each intermediate node k, it asks whether routing i→j through k is shorter — filling every pair in three nested loops.

Category

Graphs

Time complexity

O(V³)

Space complexity

O(V²)

Pseudocode

d[i][j] = direct edge or ∞
for k, for i, for j:
  d[i][j] = min(d[i][j],
             d[i][k] + d[k][j])

Reference implementation

for k in range(V):
  for i in range(V):
    for j in range(V):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Open the interactive Floyd-Warshall visualisation →