Floyd–Warshall (all-pairs shortest paths)
Problem
Given a weighted adjacency matrix (∞ where there is no edge), return the shortest distance between every pair of nodes.
Example 1
Input: [[0,3,∞,7], [8,0,2,∞], [5,∞,0,1], [2,∞,∞,0]] Output: [[0,3,5,6], [5,0,2,3], [3,6,0,1], [2,5,7,0]]
Also asked as: Implement Floyd warshallAlgorithm
Test cases
Case 1
Input: [[0,3,1000000000,7],[8,0,2,1000000000],[5,1000000000,0,1],[2,1000000000,1000000000,0]] Expected: [[0,3,5,6],[5,0,2,3],[3,6,0,1],[2,5,7,0]]
Case 2
Input: [[0,1,10],[1,0,2],[10,2,0]] Expected: [[0,1,3],[1,0,2],[3,2,0]]
Case 3
Input: [[0,5],[5,0]] Expected: [[0,5],[5,0]]
Case 4
Input: [[0]] Expected: [[0]]
View solutionHide solution1 approach
1. DP over intermediate vertices
Time O(V³)Space O(V²)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every k. Negative cycle iff any dist[i][i] < 0.
function floydWarshall(dist) { // dist[i][j] = weight or Infinity, dist[i][i] = 0 const n = dist.length; 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]; return dist;}