递推公式：

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 }