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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
|
#define MAXV 100
int D[MAXV][MAXV] = {0}; int min_path[MAXV][MAXV] = {0};
void (int A[MAXV][MAXV], int n) { int i, j, k; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { min_path[i][j] = -1; if(i == j) { D[i][j] = 0; continue; } if(A[i][j]) { D[i][j] = A[i][j]; } else { D[i][j] = 99; } }
for (k = 0; k < n; k++) { for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (D[i][j] > (D[i][k] + D[k][j])) { D[i][j] = D[i][k] + D[k][j]; min_path[i][j] = k; } } }
void print_shortest_path(int i, int j) { printf("shortest path from %d to %d is ", i, j); printf("%d ->", i); while(min_path[i][j] != -1) { printf(" %d ->", min_path[i][j]); i = min_path[i][j]; } printf(" %dn", j); }
int main() { int n = 7; int A[MAXV][MAXV] = { {0, 1, 0, 1, 1, 0, 0}, {1, 0, 1, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0, 0}, {1, 1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 1, 0} };
Floyd(A, n); int a = 2; int b = 6; printf("shortest path length from %d to %d is %dn", a, b, D[a][b]); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf("shortest path length from %d to %d is %dn", i, j, D[i][j]); } }
return 0; }
|
近期评论