-
Notifications
You must be signed in to change notification settings - Fork 4
/
floyd-warshall.c
55 lines (47 loc) 路 1.21 KB
/
floyd-warshall.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "floyd-warshall.h"
#include "stdio.h"
#include "stdlib.h"
int **AllocateMatrix(int n) {
int **m = malloc(sizeof(int *) * n);
int i;
for (i = 0; i < n; i++)
m[i] = (int *)malloc(sizeof(int) * n);
return m;
}
floyd_warshall_result FloydWarshall(graph *g) {
floyd_warshall_result result;
int **d = AllocateMatrix(g->V + 1);
int **p = AllocateMatrix(g->V + 1);
int i, j, k, n;
n = g->V;
d = g->weight;
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
p[i][j] = (d[i][j] == infinity || i == j) ? NIL_VERTEX : i;
for (k = 1; k < n; k++) {
int **d_k = AllocateMatrix(g->V + 1);
int **p_k = AllocateMatrix(g->V + 1);
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j])
d_k[i][j] = d[i][k] + d[k][j], p_k[i][j] = p[k][j];
else
d_k[i][j] = d[i][j], p_k[i][j] = p[i][j];
d = d_k;
p = p_k;
}
result.d = d;
result.p = p;
return result;
}
void PrintFloydWarshall(floyd_warshall_result result, int i, int j) {
if (i == j) {
printf("%d", i);
return;
} else if (result.p[i][j] == NIL_VERTEX)
return;
else {
PrintFloydWarshall(result, i, result.p[i][j]);
printf(" -> %d", j);
}
}