AlgoScope

Floyd-Warshall

Admit one stopover vertex per round and relax every pair through it. The matrix converges in n rounds.

Shortest path, algorithm, intermediate
1 to 1 keeps 0.0123012303∞7802∞5∞012∞∞0
1 to 1 keeps 0.0123012303∞7802∞5∞012∞∞0

All-Pairs Shortest Paths: Four vertices, three rounds of gains

Decision, step 3 of 21

(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.

Cost

Best
O(V^3)
Average
O(V^3)
Worst
O(V^3)
Space
O(V^2)