Floyd-Warshall Dynamic Programming Formulation
You'll learn: How to define the DP state and recurrence relation that powers the Floyd-Warshall algorithm for finding all-pairs shortest paths.
The Core Idea
Floyd-Warshall builds shortest paths incrementally by considering intermediate vertices. Instead of asking "what's the shortest path from A to B?", we ask: "what's the shortest path from A to B using only vertices 1 through k as intermediates?"
The key insight is that for any path, vertex k is either used or not:
- Not used: The shortest path from
itojusing vertices{1, 2, ..., k-1}remains unchanged - Used: The path goes
i → k → j, so we combine the shortest path fromitokwith the shortest path fromktoj
The DP Formulation
State Definition:
dp[k][i][j] = shortest path distance from vertex i to vertex j using only vertices {1, 2, ..., k} as intermediate nodes.
Base Case:
dp[0][i][j] = direct edge weight from i to j (or infinity if no edge exists, 0 if i == j)
Recurrence Relation:
dp[k][i][j] = min(
dp[k-1][i][j], // Don't use vertex k
dp[k-1][i][k] + dp[k-1][k][j] // Use vertex k
)
This recurrence checks both possibilities and picks the shorter path. By iterating k from 1 to n, we systematically consider all possible intermediate vertices until dp[n][i][j] contains the true shortest path from i to j.
Key Takeaway: Floyd-Warshall uses a 3D DP state where dp[k][i][j] represents the shortest path from i to j using only the first k vertices as intermediates, with a recurrence that decides whether to include vertex k in the path.