递推公式:
1.Dist(0)[i][j] = weight[i][j]
2.Dist(n)[i][j] = Min( Dist(n-1)[i][j] , Dist(n-1)[i][n] + Dist(n-1)[n][j] )
Floyd函数:
1 void Floyd(AdjMatrix* G, int Dist[][MAXVEX], int Path[][MAXVEX][MAXVEX]) 2 { 3 //Dist 路径长度 4 //若 Path[i][j][k]为1,则 k 是从 i 到 j 当前求得最短路径上的顶点 5 int i = 0, j = 0, k = 0, s = 0; 6 for (i = 0; i < G->vexnum; i++) 7 { 8 for (j = 0; j < G->vexnum; j++) 9 { 10 Dist[i][j] = G->arcs[i][j]; 11 if (Dist[i][j] < INFINITY) 12 { 13 Path[i][j][i] = 1; 14 Path[i][j][j] = 1; 15 } 16 } 17 } 18 19 for (k = 0; k < G->vexnum; k++) 20 { 21 for (i = 0; i < G->vexnum; i++) 22 { 23 for (j = 0; j < G->vexnum; j++) 24 { 25 if ((Dist[i][k] + Dist[k][j]) < Dist[i][j])//从 i 经 k 到 j 的一条路径更短 26 { 27 Dist[i][j] = Dist[i][k] + Dist[k][j]; 28 for (s = 0; s < G->vexnum; s++) 29 { 30 Path[i][j][s] = Path[i][k][s] || Path[k][j][s]; 31 } 32 } 33 } 34 } 35 } 36 }
源代码:
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <stdio.h> 3 #include <stdlib.h> 4 #define MAXVEX 20 5 #define INFINITY 32767 6 7 typedef struct 8 { 9 int vexnum, arcnum; 10 char vex[MAXVEX]; 11 int arcs[MAXVEX][MAXVEX]; 12 }AdjMatrix; 13 14 15 void Floyd(AdjMatrix* G, int Dist[][MAXVEX], int Path[][MAXVEX][MAXVEX]) 16 { 17 //Dist 路径长度 18 //若 Path[i][j][k]为1,则 k 是从 i 到 j 当前求得最短路径上的顶点 19 int i = 0, j = 0, k = 0, s = 0; 20 for (i = 0; i < G->vexnum; i++) 21 { 22 for (j = 0; j < G->vexnum; j++) 23 { 24 Dist[i][j] = G->arcs[i][j]; 25 if (Dist[i][j] < INFINITY) 26 { 27 Path[i][j][i] = 1; 28 Path[i][j][j] = 1; 29 } 30 } 31 } 32 33 for (k = 0; k < G->vexnum; k++) 34 { 35 for (i = 0; i < G->vexnum; i++) 36 { 37 for (j = 0; j < G->vexnum; j++) 38 { 39 if ((Dist[i][k] + Dist[k][j]) < Dist[i][j])//从 i 经 k 到 j 的一条路径更短 40 { 41 Dist[i][j] = Dist[i][k] + Dist[k][j]; 42 for (s = 0; s < G->vexnum; s++) 43 { 44 Path[i][j][s] = Path[i][k][s] || Path[k][j][s]; 45 } 46 } 47 } 48 } 49 } 50 } 51 52 53 int LocateVex(AdjMatrix* G, char vex) 54 { 55 int i = 0; 56 for (i = 0; i < G->vexnum; i++) 57 { 58 if (G->vex[i] == vex) 59 { 60 return i; 61 } 62 } 63 return -1; 64 } 65 66 void Create(AdjMatrix* G) 67 { 68 int weight = 0; 69 int i = 0, j = 0, k = 0; 70 char vex1 = '\0', vex2 = '\0'; 71 72 printf("请输入顶点数和弧数(逗号分隔):"); 73 scanf("%d%*c%d", &G->vexnum, &G->arcnum); 74 for (i = 0; i < G->vexnum; i++)//初始化 75 { 76 for (j = 0; j < G->vexnum; j++) 77 { 78 G->arcs[i][j] = INFINITY; 79 } 80 } 81 for (i = 0; i < G->vexnum; i++) 82 { 83 printf("请输入第%d个顶点:", i + 1); 84 scanf(" %c", &G->vex[i]); 85 } 86 for (k = 0; k < G->arcnum; k++) 87 { 88 printf("请输入第%d条弧尾、头和权值(逗号分隔):", k + 1); 89 scanf(" %c%*c%c%*c%d", &vex1, &vex2, &weight); 90 i = LocateVex(G, vex1); 91 j = LocateVex(G, vex2); 92 G->arcs[i][j] = weight; 93 } 94 } 95 96 void Print(AdjMatrix* G, int Dist[][MAXVEX], int Path[][MAXVEX][MAXVEX]) 97 { 98 int i = 0, j = 0, k = 0; 99 for (i = 0; i < G->vexnum; i++) 100 { 101 for (j = 0; j < G->vexnum; j++) 102 { 103 if (i == j) 104 { 105 continue; 106 } 107 printf("%c->%c最短路径长度为%d,经过顶点:", G->vex[i], G->vex[j], Dist[i][j]); 108 for (k = 0; k < G->vexnum; k++) 109 { 110 if (Path[i][j][k]) 111 { 112 printf("%c ", G->vex[k]); 113 } 114 } 115 printf("\n"); 116 } 117 } 118 } 119 120 int main(void) 121 { 122 int Dist[MAXVEX][MAXVEX] = { 0 };//路径长度 123 int Path[MAXVEX][MAXVEX][MAXVEX] = { 0 };//若 Path[i][j][k]为1,则 k 是从 i 到 j 当前求得最短路径上的顶点 124 AdjMatrix G; 125 Create(&G); 126 Floyd(&G, Dist, Path); 127 Print(&G, Dist, Path); 128 system("pause"); 129 return 0; 130 }源代码