This program finds shortest paths, except that sometimes it does not. The cause is one famous mistake.
What to build
A correct Floyd–Warshall, made by repairing the program you are given.
Requirements
- Keep the same comparison inside the loops.
- Make the distance between every pair correct.
- Keep the output format as it is.
Input
The first line has n and m. Each of the next m lines has a directed edge u v w.
Output
n lines of n values separated by spaces: the shortest distance from each vertex to each vertex, or INF if there is no route.
Constraints
1 ≤ n ≤ 30, 0 ≤ m ≤ 500, 1 ≤ w ≤ 1000, and no two edges join the same ordered pair.
Example
Input:
4 3
0 3 1
3 2 1
2 1 1
Output:
0 3 2 1
INF 0 INF INF
INF 1 0 INF
INF 2 1 0
Why it works
After the round for k, d[i][j] is the best route using only stops up to k. That only holds if every pair has been finished for k − 1 first, which needs k on the outside.
Examples
4 3 0 3 1 3 2 1 2 1 1
0 3 2 1 INF 0 INF INF INF 1 0 INF INF 2 1 0
2 1 0 1 7
0 7 INF 0
Hints
Hint 1
Look at the order of the three loops.
Hint 2
`k` says which vertices may be used as stops. It has to change last of all, so it must be the outermost loop.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#define INF 99999999
int main(void) {
int n, m, d[30][30];
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = i == j ? 0 : INF;
for (int e = 0; e < m; e++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
d[u][v] = w;
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
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) printf("INF ");
else printf("%d ", d[i][j]);
}
printf("\n");
}
return 0;
}