Floyd–Warshall Algorithm

Practice this coding question on Coding Gurukul.

Problem statement

Given a directed weighted graph, use Floyd–Warshall to find the shortest distance between every pair of vertices. Print an n by n distance matrix. Entry [u][v] is the shortest distance from u to v. Print INF if v is unreachable from u. Every diagonal entry is 0. Negative edge weights are allowed, but there are no negative-weight cycles. For repeated edges, use the smallest weight. Use signed 64-bit distances, O(n^3) time and O(n^2) space. Worked example The path 0→1→2 costs 4-1=3, which is less than 10. No paths lead from 1 or 2 back to 0, so those entries are INF.

Input format

First line: n m. Next m lines: directed edge u v w.

Output format

Print n rows of n space-separated distances or INF, in vertex order.

Constraints

1 <= n <= 150; 0 <= m <= 20000; 0 <= u,v < n; -10^6 <= w <= 10^6. No negative-weight cycles.

Sample input

3 3
0 1 4
1 2 -1
0 2 10

Sample output

0 4 3
INF 0 -1
INF INF 0

Sign in to run or submit a solution in C++, Java or Python.