Sign in to watch this lesson
Algorithms - Graphs II · 4:23
Floyd-Warshall
Floyd-Warshall computes the distance between every pair of vertices, negative edges included, with three nested loops and one line of arithmetic. We sweep the phases on a four-vertex graph with a rebate edge, prove why k must be the outer loop (and show the wrong cell the other order produces), restore routes from stored phases, detect negative cycles on the diagonal, and fix the INT_MAX infinity overflow.
You will learn
- State the phase invariant of Floyd-Warshall and derive the update d[i][j] = min(d[i][j], d[i][k] + d[k][j])
- Run the algorithm by hand on a small graph with a negative edge, and explain why k must be the outermost loop
- Restore a shortest route from stored phases and detect negative cycles from the diagonal
- Avoid infinity overflow (guard, long long 1e18 or 0x3f3f3f3f) and use bitsets for transitive closure