Floyd-Warshall
Admit one stopover vertex per round and relax every pair through it; the matrix converges in n rounds.
Decision · step 3 of 21All-Pairs Shortest Paths: Four vertices, three rounds of gains
(1, 1): via 0 costs dist[1][0] + dist[0][1] = 8 + 3 = 11, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
What you will see
The distance matrix updates for each k; cell (i, j) reads (i, k) and (k, j) with dependency arrows.
Cost
| Best | O(V^3) |
|---|---|
| Average | O(V^3) |
| Worst | O(V^3) |
| Space | O(V^2) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, tentative distance and parent; each step announces the relaxation and whether it improved a distance.
Reduced motion: Distance updates change the label with a crossfade instead of radiating from the edge.