Path Reconstruction in Floyd-Warshall
You'll learn how to not just find shortest distances, but also rebuild the actual paths that achieve them.
The Missing Piece
So far, Floyd-Warshall tells you the shortest distance between any two vertices—but what if you need to know which vertices to visit to achieve that distance? Just like you learned with Dijkstra's predecessor array, we need a way to trace back through our computed results.
The Predecessor Matrix Approach
While Floyd-Warshall computes a distance matrix dist[i][j], we maintain a parallel predecessor matrix (often called next[i][j]). This matrix stores: "To get from i to j optimally, what's the first vertex I should go to after i?"
Initialization:
- Set
next[i][j] = jfor all direct edges (initially, go straight toj) - Set
next[i][j] = -1if no path exists
During the algorithm:
When you update a distance through an intermediate vertex k:
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k] // Follow the path through k
The key insight: if going through k improves the path from i to j, then the next step from i should be whatever we'd use to reach k.
Reconstructing the Path
To rebuild the path from u to v:
- Start at
u - Follow
next[u][v]to get the next vertex - Repeat until you reach
v
Key Takeaway: By maintaining a predecessor/next matrix alongside distances in Floyd-Warshall, you can reconstruct the entire shortest path between any vertex pair, not just compute its length.