弗洛伊德算法（Floyd算法）

                1
                //
                 邻接矩阵
                2 typedef struct _graph
3{
4char vexs[MAX];       // 顶点集合5int vexnum;           // 顶点数6int edgnum;           // 边数7int matrix[MAX][MAX]; // 邻接矩阵8 }Graph, *PGraph;

                 1
                /*
                 2
                 * floyd最短路径。

                 3
                 * 即，统计图中各个顶点间的最短路径。

                 4
                 *

                 5
                 * 参数说明：

                 6
                 *        G -- 图

                 7
                 *     path -- 路径。path[i][j]=k表示，"顶点i"到"顶点j"的最短路径会经过顶点k。

                 8
                 *     dist -- 长度数组。即，dist[i][j]=sum表示，"顶点i"到"顶点j"的最短路径的长度是sum。

                 9
                */
                10
                void floyd(Graph G, int path[][MAX], int dist[][MAX])
11{
12int i,j,k;
13int tmp;
1415// 初始化16for (i = 0; i < G.vexnum; i++)
17    {
18for (j = 0; j < G.vexnum; j++)
19        {
20             dist[i][j] = G.matrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。21             path[i][j] = j;                 // "顶点i"到"顶点j"的最短路径是经过顶点j。22        }
23    }
2425// 计算最短路径26for (k = 0; k < G.vexnum; k++)
27    {
28for (i = 0; i < G.vexnum; i++)
29        {
30for (j = 0; j < G.vexnum; j++)
31            {
32// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]33                 tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
34if (dist[i][j] > tmp)
35                {
36// "i到j最短路径"对应的值设，为更小的一个(即经过k)37                     dist[i][j] = tmp;
38// "i到j最短路径"对应的路径，经过k39                     path[i][j] = path[i][k];
40                }
41            }
42        }
43    }
4445// 打印floyd最短路径的结果46     printf("floyd: \n");
47for (i = 0; i < G.vexnum; i++)
48    {
49for (j = 0; j < G.vexnum; j++)
50             printf("%2d  ", dist[i][j]);
51         printf("\n");
52    }
53 }