Course contentsShow
← Computer Science
Lesson 992 of 2,87223. Shortest Path AlgorithmsFree lesson

Floyd-Warshall Dynamic Programming Formulation

Defining the DP state and recurrence relation for computing shortest paths through intermediate vertices.

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 i to j using vertices {1, 2, ..., k-1} remains unchanged
  • Used: The path goes i → k → j, so we combine the shortest path from i to k with the shortest path from k to j

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.