Floyd Warshall

Time: O(V^3)

Space: O(V^2)

Intuition

All-pairs shortest paths using dynamic programming over intermediate nodes. dist[i][j] = shortest path from i to j. For each intermediate node k: if going through k is shorter, update. Three nested loops: k (intermediate), i (source), j (destination).

Algorithm

1Initialise dist from adjacency matrix. dist[i][i]=0.
2For k from 0 to V-1: for i,j: dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]).
3Return dist matrix.

Example Walkthrough

Input: V=4, edges: 0â†’1(5),0â†’3(10),1â†’2(3),2â†’3(1)

1.k=0: no improvement. k=1: dist[0][2]=min(âˆž,5+3)=8. k=2: dist[0][3]=min(10,8+1)=9.

Output: Shortest paths: 0â†’3=9

Common Pitfalls

•k must be the OUTER loop â€” intermediate nodes are added one at a time.

Floyd Warshall.java

Java

// Approach: All-pairs shortest path DP. dist[i][j] = min over intermediate vertices k of (dist[i][k] + dist[k][j]).
// Time: O(V^3) Space: O(V^2)
class Solution {
    public void floydWarshall(int[][] dist) {
        int n = dist.length;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Was this solution helpful?