Floyd warshall algorithm
HardAll-pairs shortest paths by trying every middle node
Problem
Compute shortest distances between all pairs of nodes.
Try every node as a middle stop, improving each pair's distance — all shortest paths at once.
The idea
Floyd-Warshall fills a distance table by allowing more and more stepping-stones. After the round for node k, dist[i][j] holds the shortest path that only passes through intermediate nodes 0..k. Adding node k just asks a question for every pair: is going i → k → j cheaper than what I already have? Three nested loops, O(V³), and you get every pair at once.
The trick
- After the round for k, every dist[i][j] already uses the best path through nodes 0..k only.
- The k-loop must be outermost — it defines which intermediates are allowed so far.
Step 1 of 11. Floyd-Warshall finds the shortest distance between every pair of nodes. Here is the weighted graph we will measure.
1dist[i][j] = edge(i,j) or ∞, and dist[i][i] = 02for k in nodes: // stepping-stone3 for i, for j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])4return dist // all-pairs shortest distancesInput
- nodes
- 4, 5 edges
Memory
- cells marked
- —
- rows
- —
- cols
- —
- via k
- —
Output
- all-pairs
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n=4, edges=[[0,1,3],[1,2,1],[2,3,2],[0,3,10]]
- Output:
- [[0, 3, 4, 6], ['INF', 0, 1, 3], ['INF', 'INF', 0, 2], ['INF', 'INF', 'INF', 0]]
- Explanation:
- All-pairs shortest distances.
Example 2
- Input:
- n=2, edges=[[0,1,5]]
- Output:
- [[0, 5], ['INF', 0]]
- Explanation:
- 0→1 = 5; 1→0 unreachable.
Example 3
- Input:
- n=3, edges=[[0,1,1],[1,2,1]]
- Output:
- [[0, 1, 2], ['INF', 0, 1], ['INF', 'INF', 0]]
- Explanation:
- 0→2 via 1 costs 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.