Floyd-Warshall
Admit one stopover vertex per round and relax every pair through it. The matrix converges in n rounds.
All-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.
Cost
- Best
- O(V^3)
- Average
- O(V^3)
- Worst
- O(V^3)
- Space
- O(V^2)