Question

为了能讲明白弗洛伊德（Floyd）算法的精妙所在，我们先来看最简单的案例。图7-7-12的左图是一个最简单的3个顶点连通网图。

图7-7-12

我们先定义两个二维数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵。P代表对应顶点的最小路径的前驱矩阵，用来存储路径。在未分析任何顶点之前，我们将D命名为D_-1，其实它就是初始的图的邻接矩阵。将P命名为P_-1，初始化为图中所示的矩阵。

首先我们来分析，所有的顶点经过v₀后到达另一顶点的最短路径。因为只有三个顶点，因此需要查看v_-1→v₀→v₂，得到D_-1[1][0]+D_-1[0][2]=2+1=3。D_-1[1][2]表示的是v₁→v₂的权值为5，我们发现D_-1[1][2]>D_-1[1][0]+D_-1[0][2]，通俗的话讲就是v₁→v₀→v₂比直接v₁→v₂距离还要近。所以我们就让D_-1[1][2]=D_-1[1][0]+D_-1[0][2]=3，同样的D_-1[2][1]=3，于是就有了D₀的矩阵。因为有变化，所以P矩阵对应的P_-1[1][2]和P_-1[2][1]也修改为当前中转的顶点v₀的下标0，于是就有了P₀。也就是说D₀[v][w]=min{D_-1[v][w],D_-1[v][0]+D_-1[0][w]}

接下来，其实也就是在D₀和P₀的基础上继续处理所有顶点经过v₁和v₂后到达另一顶点的最短路径，得到D₁和P₁、D₂和P₂完成所有顶点到所有顶点的最短路径计算工作。

如果我就用这么简单的图形来讲解代码，大家一定会觉得不能说明什么问题。所以我们还是以前面的复杂网图为例，来讲解弗洛伊德（Floyd）算法。

首先我们针对图7-7-13的左网图准备两个矩阵D_-1和P_-1，D_-1就是网图的邻接矩阵，P_-1初设为P[i][j]=j这样的矩阵，它主要用来存储路径。

图7-7-13

代码如下，注意因为是求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* Floyd算法，求网图G中各顶点v到其余顶点w最短
   路径P[v][w]及带权长度D[v][w] */
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, 
                        ShortPathTable *D)
{
    int v, w, k;
    /* 初始化D与P */
    for (v = 0; v < G.numVertexes; ++v)         
       for (w = 0; w < G.numVertexes; ++w)
        {
           /* D[v][w]值即为对应点间的权值 */
           (*D)[v][w] = G.matirx[v][w];        
           /* 初始化P */
           (*P)[v][w] = w;                     
        }
    }
    for (k = 0; k < G.numVertexes; ++k)
    {
        for (v = 0; v < G.numVertexes; ++v)
        {
            for (w = 0; w < G.numVertexes; ++w)
            {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
                {                               
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    /* 将当前两点间权值设为更小的一个 */
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    /* 路径设置经过下标为k的顶点 */
                    (*P)[v][w] = (*P)[v][k];    
                }
            }
        }
    }
}

1．程序开始运行，第4～11行就是初始化了D和P，使得它们成为图7-7-13的两个矩阵。从矩阵也得到，v₀→v₁路径权值是1，v₀→v₂路径权值是5，v₀→v₃无边连线，所以路径权值为极大值65535。

2．第12～25行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。

3．当K=0时，也就是所有的顶点都经过v₀中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如图7-7-14所示。

图7-7-14

4．当K=1时，也就是所有的顶点都经过v₁中转。此时，当v=0时，原本D[0][2]=5，现在由于D[0][1]+D[1][2]=4。因此由代码的第20行，二者取其最小值，得到D[0][2]=4，同理可得D[0][3]=8、D[0][4]=6，当v=2、3、4时，也修改了一些数据，请参考如图7-7-15左图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要作处理，将它们都改为当前的P[v][k]值，见代码第21行。

图7-7-15

5．接下来就是k=2一直到8结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D₀是以D_-1为基础，D₁是以D₀为基础，……，D₈是以D₇为基础，就像我们曾经说过的七个包子的故事，它们是有联系的，路径矩阵P也是如此。最终当k=8时，两矩阵数据如图7-7-16所示。

图7-7-16

至此，我们的最短路径就算是完成了，你可以看到矩阵第v₀行的数值与迪杰斯特拉（Dijkstra）算法求得的D数组的数值是完全相同，都是{0,1,4,7,5,8,10,12,16}。而且这里是所有顶点到所有顶点的最短路径权值和都可以计算出。

那么如何由P这个路径数组得出具体的最短路径呢？以v₀到v₈为例，从图7-7-16的右图第v₈列，P[0][8]=1，得到要经过顶点v₁，然后将1取代0得到P[1][8]=2，说明要经过v₂，然后将2取代1得到P[2][8]=4，说明要经过v₄，然后将4取代2得到P[4][8]=3，说明要经过v₃，……，这样很容易就推导出最终的最短路径值为v₀→v₁→v₂→v₄→v₃→v₆→v₇→v₈。

求最短路径的显示代码可以这样写。

for (v = 0; v < G.numVertexes; ++v)
{
    for (w = v + 1; w < G.numVertexes; w++)
    {
        printf("v%d-v%d weight: %d ", v, w, D[v][w]);
        /* 获得第一个路径顶点下标 */
        k = P[v][w];                
        /* 打印源点 */
        printf(" path: %d", v);     
        /* 如果路径顶点下标不是终点 */
        while (k != w)              
        {
            /* 打印路径顶点 */
            printf(" -> %d", k);    
            /* 获得下一个路径顶点下标 */
            k = P[k][w];            
        }
        /* 打印终点 */
        printf(" -> %d\n", w);      
    }
    printf("\n");
}

再次回过头来看看弗洛伊德（Floyd）算法，它的代码简洁到就是一个二重循环初始化加一个三重循环权值修正，就完成了所有顶点到所有顶点的最短路径计算。几乎就如同是我们在学习C语言循环嵌套的样例代码而已。如此简单的实现，真是巧妙之极，在我看来，这是非常漂亮的算法，不知道你们是否喜欢？很可惜由于它的三重循环，因此也是O(n³)时间复杂度。如果你面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德（Floyd）算法应该是不错的选择。

另外，我们虽然对求最短路径的两个算法举例都是无向图，但它们对有向图依然有效，因为二者的差异仅仅是邻接矩阵是否对称而已。