Floyd-Warshall All-Pairs Shortest Paths (2D)

Graph

Vertices 4

Algorithm playback

Speed (relaxations/s) 20

Shortest-path query

Source

Target

Or click two nodes on the graph directly — first click sets source, second sets target.

Live readout

Pivot k

–

Relaxations applied

Steps done

0 / 0

Path distance

–

How it works

Floyd-Warshall computes every pair's shortest path with three nested loops — the real, unmodified dynamic-programming recurrence, executed here one (k, i, j) triple at a time so you can watch it happen:

for k in 0..n-1:
  for i in 0..n-1:
    for j in 0..n-1:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        next[i][j] = next[i][k]

After pivot k finishes, dist[i][j] is guaranteed optimal among paths that only pass through intermediate vertices 0..k — that invariant is why running k as the outer loop is correct. The heatmap on the right is the live dist matrix; a cell flashes green the instant a relaxation improves it, and the current pivot's row and column are outlined.

next[i][j] — a next-hop matrix updated in lock-step with dist; following it from a source to a target reconstructs the actual shortest path, not just its length.
∞ — no path found yet between that pair at the current point in the run.
Click two nodes — the shortest known route between them (valid even mid-run, per the invariant above) is traced in purple on the graph.

Graph edges Queried shortest path Just-relaxed cell