Practice › Graphs
Floyd-Warshall All-Pairs Shortest Paths
Medium · Graphs · Asked at Amazon, Google, Samsung
The graph is directed with non-negative weights (there can be several edges between the same pair). Print the shortest distance between every pair of nodes as an n × n matrix: row i, column j is the distance from i to j, or -1 if j is unreachable from i. The distance from a node to itself is 0.
Input
First line: n m. Next m lines: u v w — an edge from u to v with weight w.
Output
n lines of n integers.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ m ≤ 10^4
- 0 ≤ w ≤ 1000
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for every intermediate node k in the outer loop.
Example 1
Input
4 5 1 2 3 2 3 1 1 3 7 3 4 2 4 1 1
Output
0 3 4 6 4 0 1 3 3 6 0 2 1 4 5 0
Example 2
Input
2 2 1 2 5 1 2 3
Output
0 3 -1 0
Hints
- dist[i][j] starts as the cheapest direct edge (0 on the diagonal, ∞ if none).
- For each k, allow k as an intermediate node: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). k must be the outermost loop.
Approach
After processing intermediate nodes 1..k, dist[i][j] is the shortest path using only those as stops. Adding node k only requires checking paths that go through it. Keep the minimum of parallel edges when reading. At the end, print −1 for infinite distances.
Complexity: O(n³) time · O(n²) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
const long long INF = LLONG_MAX / 4;
vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
for (int i = 1; i <= n; i++) d[i][i] = 0;
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; 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 = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cout << (d[i][j] >= INF ? -1 : d[i][j]) << (j < n ? " " : "\n");
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
INF = float("inf")
d = [[0 if i == j else INF for j in range(n + 1)] for i in range(n + 1)]
for i in range(m):
u, v, w = data[2 + 3 * i], data[3 + 3 * i], data[4 + 3 * i]
d[u][v] = min(d[u][v], w)
for k in range(1, n + 1):
dk = d[k]
for i in range(1, n + 1):
dik = d[i][k]
if dik == INF:
continue
di = d[i]
for j in range(1, n + 1):
if dik + dk[j] < di[j]:
di[j] = dik + dk[j]
print("\n".join(" ".join(str(-1 if x == INF else x) for x in row[1:]) for row in d[1:]))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long INF = Long.MAX_VALUE / 4;
long[][] d = new long[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
Arrays.fill(d[i], INF);
d[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
long w = sc.nextLong();
d[u][v] = Math.min(d[u][v], w);
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) sb.append(d[i][j] >= INF ? -1 : d[i][j]).append(j < n ? " " : "\n");
System.out.print(sb);
}
}Solve Floyd-Warshall All-Pairs Shortest Paths online · All practice problems