Floyd Warshall — Solution in Python, Java & C++
Floyd Warshall solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Floyd Warshall is a medium coding problem on dynamic programming, graph and shortest path, asked in Amazon, Flipkart and Samsung interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Graph, Shortest Path
- Asked at: Amazon, Flipkart, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A weighted directed graph with n vertices, numbered 0 to n - 1, is given as an n x n adjacency matrix matrix:
matrix[i][j]is the weight of the edge fromitoj, or-1if there is no such edge,matrix[i][i]is always0.
Return the matrix of shortest distances: entry [i][j] is the length of the shortest path from i to j, or -1 if j cannot be reached from i. A vertex is at distance 0 from itself.
Example 1
Input: matrix = [[0,25],[-1,0]]
Output: [[0,25],[-1,0]]
Explanation: Vertex 1 has no outgoing edge, so it reaches nothing but itself.
Example 2
Input: matrix = [[0,1,43],[1,0,6],[-1,-1,0]]
Output: [[0,1,7],[1,0,6],[-1,-1,0]]
Explanation: Going 0 → 1 → 2 costs 1 + 6 = 7, cheaper than the direct edge of 43.
Example 3
Input: matrix = [[0]]
Output: [[0]]
Constraints
1 <= n <= 100matrix.length == matrix[i].length == nmatrix[i][i] == 0matrix[i][j] == -1 or 1 <= matrix[i][j] <= 1000 for i != j
Hints for Floyd Warshall
Hint 1
A shortest path from
itojeither avoids vertexkor goesi → … → k → … → j, joining two shorter shortest paths.Hint 2
Let
d[i][j]be the best distance using only intermediate vertices from{0, …, k}. Adding vertexkcan only improved[i][j]tod[i][k] + d[k][j].Hint 3
Treat
-1as infinity while relaxing, loopkoutermost, and turn infinity back into-1at the end.
How to solve Floyd Warshall
Floyd–Warshall is a dynamic programme over the set of vertices a path may pass through. After processing vertices 0..k as possible intermediates, d[i][j] holds the shortest i → j path whose interior uses only those vertices.
Approach
- Copy the matrix, replacing every
-1with a large sentinelINF(any value above the longest possible path, e.g.10^8). - For
kfrom0ton - 1, for every pair(i, j): ifd[i][k] + d[k][j] < d[i][j], updated[i][j]. - Replace every entry still at
INFwith-1and return the matrix.
Why it works
Consider the shortest i → j path whose interior vertices are all below k + 1. If it does not use k, it was already found in round k - 1. If it does, it visits k once (weights are positive, so a cycle never helps), splitting into an i → k and a k → j path whose interiors are below k — both already optimal in d — so the update in round k finds it. By induction the final table is exact.
Complexity
- Time —
O(n^3) - Space —
O(n^2)
Pitfalls
- The loop over the intermediate vertex
kmust be the outermost one; putting it inside thei/jloops gives wrong answers. - Do not add to
-1directly — convert it to a sentinel first, or a missing edge looks like a negative shortcut. - Keep the sentinel small enough that
INF + INFcannot overflow a 32-bit integer.
Reference solution
Python
from typing import List
def shortestDistance(matrix: List[List[int]]) -> List[List[int]]:
n = len(matrix)
INF = 10 ** 8
d = [[INF if v == -1 else v for v in row] for row in matrix]
for k in range(n):
dk = d[k]
for i in range(n):
dik = d[i][k]
if dik == INF:
continue
di = d[i]
for j in range(n):
if dik + dk[j] < di[j]:
di[j] = dik + dk[j]
return [[-1 if v >= INF else v for v in row] for row in d]Java
public static int[][] shortestDistance(int[][] matrix) {
int n = matrix.length, INF = 100000000;
int[][] d = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = matrix[i][j] == -1 ? INF : matrix[i][j];
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) {
if (d[i][k] == INF) continue;
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (d[i][j] >= INF) d[i][j] = -1;
return d;
}C++
vector<vector<int>> shortestDistance(vector<vector<int>>& matrix) {
int n = matrix.size(), INF = 100000000;
vector<vector<int>> d(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = matrix[i][j] == -1 ? INF : matrix[i][j];
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) {
if (d[i][k] == INF) continue;
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
for (auto& row : d)
for (auto& v : row) if (v >= INF) v = -1;
return d;
}JavaScript
var shortestDistance = function(matrix) {
var n = matrix.length, INF = 100000000;
var d = [];
for (var i = 0; i < n; i++) {
var row = [];
for (var j = 0; j < n; j++) row.push(matrix[i][j] === -1 ? INF : matrix[i][j]);
d.push(row);
}
for (var k = 0; k < n; k++) {
for (var a = 0; a < n; a++) {
if (d[a][k] === INF) continue;
for (var b = 0; b < n; b++) {
if (d[a][k] + d[k][b] < d[a][b]) d[a][b] = d[a][k] + d[k][b];
}
}
}
for (var x = 0; x < n; x++) for (var y = 0; y < n; y++) if (d[x][y] >= INF) d[x][y] = -1;
return d;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Graph Data Structure