Pattern Guide
Floyd-Warshall All-Pairs Shortest Paths
"O(V³) all-pairs shortest paths. Transitive closure, detect negative cycles."
Floyd-Warshall computes shortest paths between every pair of vertices in O(V³). Key insight: dp[k][i][j] = shortest path from i to j using only vertices 0..k as intermediates. Optimized to 2D: for each intermediate vertex k, relax all pairs. Detects negative cycles if any dp[i][i] < 0 after completion. Also computes transitive closure (reachability).
Problems you can solve with this pattern
3 problems · click any to start solving
function floydWarshall(n, edges) {
// Initialize distance matrix
const dist = Array.from({length: n}, (_, i) =>
Array.from({length: n}, (_, j) => i === j ? 0 : Infinity)
);
// Add edges
for (const [u, v, w] of edges) {
dist[u][v] = Math.min(dist[u][v], w);
// dist[v][u] = w; // for undirected
}
// Relax through each intermediate vertex
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
// Check for negative cycles
for (let i = 0; i < n; i++)
if (dist[i][i] < 0) return null; // negative cycle
return dist;
}Floyd-Warshall: initialize dist[i][j] = weight of edge (i,j) or Infinity if no edge, dist[i][i] = 0. For k from 0 to n-1: for all i,j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After n iterations, dist[i][j] = shortest path. If dist[i][i] < 0, negative cycle exists. For transitive closure: use boolean OR instead of min.
function floydWarshall(n, edges) {
// Initialize distance matrix
const dist = Array.from({length: n}, (_, i) =>
Array.from({length: n}, (_, j) => i === j ? 0 : Infinity)
);
// Add edges
for (const [u, v, w] of edges) {
dist[u][v] = Math.min(dist[u][v], w);
// dist[v][u] = w; // for undirected
}
// Relax through each intermediate vertex
for (let k = 0; k < n; k++)
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
// Check for negative cycles
for (let i = 0; i < n; i++)
if (dist[i][i] < 0) return null; // negative cycle
return dist;
}- Dijkstra: O(E log V) per source, O(VE log V) for all-pairs
- Floyd-Warshall: O(V³) — better when V is small (< 500) and graph is dense
- Floyd-Warshall handles negative edges (but not negative cycles)
Applications:
- All-pairs shortest paths in dense graphs
- Transitive closure (reachability)
- Detect negative cycles (diagonal becomes negative)
- Find shortest path through required intermediate nodes
Optimization: If only specific pairs needed, multiple Dijkstra runs may be faster than Floyd-Warshall.