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.