Floyd–Warshall (all-pairs shortest paths)

Medium

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]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}