Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. dist[i][j] starts as the cheapest direct edge (0 on the diagonal, ∞ if none).
  2. 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