Graph Patterns: All-Pairs Shortest Path (Floyd-Warshall)
Dijkstra's Algorithm finds the shortest path from a single starting node to all others. But what if you need a lookup table for the shortest path between *every* possible pair of cities?
Introduction
The Floyd-Warshall algorithm is fundamentally a Dynamic Programming (DP) solution applied to graphs. It builds an entire adjacency matrix where matrix[i][j] represents the absolute shortest path from node i to node j.
The Matrix Logic
The algorithm uses three nested loops, giving it a time complexity of $O(V^3)$.
The outermost loop represents an intermediate node k. The inner loops iterate through all starting nodes i and all destination nodes j.
For every pair of nodes, we ask a simple question: Is it shorter to go directly from i to j, or is it shorter to take a detour through node k?
By systematically testing every node as an intermediate "detour" for every other pair, the matrix eventually converges to hold the absolute optimal distances across the entire graph.
Implementation
class Solution {
public void floydWarshall(int[][] matrix) {
int V = matrix.length;
// Initialize unreachable edges with a large value
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = (int)(1e9);
}
if (i == j) matrix[i][j] = 0;
}
}
// The core DP logic: k is the intermediate node
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
matrix[i][j] = Math.min(
matrix[i][j],
matrix[i][k] + matrix[k][j]
);
}
}
}
// Revert unreachable large values back to -1
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (matrix[i][j] == (int)(1e9)) {
matrix[i][j] = -1;
}
}
}
}
}