Floyd-Warshall: All-Pairs Shortest Paths
Fill the all-pairs distance matrix using the three-nested-loop Floyd-Warshall algorithm and apply it to find the smallest number of hops between all node pairs.
All-Pairs Shortest Paths
Floyd-Warshall computes shortest paths between every pair of nodes in a weighted graph — including graphs with negative edge weights (but not negative cycles). Running Dijkstra from each source takes O(V × (V+E) log V); Floyd-Warshall runs in O(V³) regardless of edge density. For dense graphs with V ≤ 500, Floyd-Warshall is often simpler and comparably fast.
The Core Idea: Intermediate Nodes
Floyd-Warshall's insight: dp[i][j][k] = shortest path from i to j using only nodes {0, 1, ..., k} as intermediates. Either the shortest path uses node k as an intermediate, or it doesn't. If it does: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. If not: dp[i][j][k] = dp[i][j][k-1]. Since the third dimension only progresses forward, it can be eliminated — we update in-place.
All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction