弗洛伊德算法思想篇

之前一篇文章 图解：最短路径之迪杰斯特拉算法 中谈到如何解决图中任意两个顶点之间最短路径的计算问题，今日就是围绕这个问题展开。

景禹： 不知小禹禹回去之后可有思考如何解决？

小禹禹： 那必须的，我看迪杰斯特拉算法可以计算指定顶点到其他顶点之间的最短路径，那么我就可以通过指定网络中的每一个顶点为源点，重复执行迪杰斯特拉算法 n 次，这样便可以得到每一对顶点之间的最短路径，显然这种方式的时间复杂度为\(O(n^3)\) 。

景禹： 小禹禹真是聪明，这的确不失为一个好方法，今日所讲的算法时间复杂度也为\(O(n^3)\) ，但是她的实现比小禹禹的那种方式更加简洁优雅，重要的是思想也很巧妙，她就是 弗洛伊德（Floyd）算法 。

迪杰斯特拉算法计算指定顶点到其他顶点之间的最短路径需要维护一个长度为 n 的辅助向量 D。而弗洛伊德算法既然可以求得每一对顶点之间的最短路径，自然要维护一个\(n\times n\) 的二维辅助向量 D，同理也需要维护一个\(n\times n\) 的二维路径向量 P。接下来你所看到的就是弗洛伊德算法最核心的部分了。

现定义一个 n 阶方阵序列

\(D^{-1},D^0,D^1,...,D^k,...,D^{n-1}\)

其中

\(D^{-1}[i][j]=G.arcs[i][j]\)

\(D^k[i][j]=Min\{D^{k-1}[i][j],D^{k-1}[i][k]+D^{k-1}[k][j]\}0\le k\le n-1\)

(小禹禹心想，我怎么这么难呀，别让我看了。“不能放弃奥”)，其中方阵\(D^{-1}\) 就是我们图的邻接矩阵，\(D^1[i][j]\)表示从顶点\(V_i\) 到顶点\(V_j\)的中间顶点的序号不大于 1 的最短路径的长度；\(D^k[i][j]\)表示从顶点 \(V_i\) 到顶点\(V_j\) 的中间顶点的序号不大于 k 的最短路径的长度；\(D^{n-1}[i][j]\)表示从顶点\(V_i\) 到顶点\(V_j\) 的最短路径的长度；

小禹禹： 景禹，弗洛伊德这样看上去是简洁，可我也看不懂呀！

景禹： 那就让我一起愉快地看栗子吧！

我们先以上面包含三个顶点个无向图来讲解弗洛伊德算法的思想，然后再使用在将迪杰斯特拉算法时用到的图上人脑模拟一遍。

细心的小禹禹一定发现，图中包含三个顶点的邻接矩阵的右上角标注的是\(D^0\) ,这是为什么呢？不是说好的 n 阶方阵\(D^{-1}\) 初始化为图的邻接矩阵吗？

景禹： 这就得感慨数学的严谨性质了，除 n 阶方阵\(D^{-1}\)之外，其他任何一个 n 阶方阵都可以使用它的前一个状态获得，则：

\(D^0[i][j]=Min\{D^{-1}[i][j],D^{-1}[i][0]+D^{-1}[0][j]\}=Min\{G.arcs[i][j],G.arcs[i][0]+G.arcs[0][j]\}=D_{-1}\)

， 故 n 阶矩阵 \(D^{-1}\)和\(D^0\)是同一个矩阵。那么\(D^1\) 如何求得呢？当然是用她的前一个状态\(D^0\) 求得了

\(D^1[i][j]=Min\{D^0[i][j],D^0[i][1]+D^0[1][j]\}\)

比如计算顶点\(V_0\)到顶点\(V_2\)的最短路径，

\(D^1[0][2]=Min\{D^0[0][2],D^0[0][1]+D^0[1][2]\}\)

，其中\(D^0[0][2]\)的值为5，即顶点\(V_0\)到顶点\(V_2\)的直接距离为 5；而\(D^0[0][1]+D^0[1][2]=1+3=4\)，表示顶点\(V_0\)到顶点\(V_2\)经顶点\(V_1\)中转以后的距离为4，从而将\(D^1[0][2]\)更新为4，表示顶点\(V_0\)到顶点 \(V_2\)的最短路径为4。

这就是弗洛伊德算法的精妙所在，在一个图中，要求得任意两个顶点\(V_i\)和\(V_j\)之间的最短路径，我们则可以通过两个顶点\(V_i\)和\(V_j\)之间的顶点进行中转，对于算法本身而言，则是不断得尝试所有的中转结点，从而确定两个顶点之间的最短路径。

根据公式计算完之后，获得 n 阶矩阵 .

弗洛伊德算法执行过程演示

为了更清楚弗洛伊德算法的执行过程，和弗洛伊德算法的精妙所在，我们以下图为例，一步一步得脑子过一遍。

算法第一步，初始化 n 阶矩阵 D（辅助向量） 和n 阶矩阵P（路径向量）：

\(P[i][j]\)表示从\(V_i\)到\(V_j\)路径上最后一个点，也就是\(V_i\to V_j=V_i\to V_{j-1}+P[i][j]\)，这样倒序就能找到路径上所有的点。

第二步：k == 1，此时

\(D^1[i][j]=Min\{D^0[i][j],D^0[i][1]+D^0[1][j]\}\)

我们主要就是计算\(D^0[i][1]+D^0[1][j]\) ，其中\(D^0[i][1]\)就是下方我们所标记的绿色列，而\(D^0[i][1]+D^0[1][j]\)则表示我们所标记的绿色行。这样我想大家就可以进行轻松计算了，我们以取 i == 0 为例进行计算，则\(D^0[0][1]=1\)，分别与\(D^0[1][j]\)所表示的绿色行中的每一个元素进行相加，即得到 [2,1,4,8,6,1+∞,1+∞,1+∞,1+∞]，然后与\(V_0\)的行[0,1,5,∞,∞,∞,∞,∞,∞] 进行大小比较，将更小值保留，即得到\(D^1\)中的\(V_0\)行；此时相应的只要将\(P^1[0][j]\)更新为\(P^0[0][1]\) 。红色表示被更新过的元素。(我们发现更新的其实只有右下角的部分！)

第三步：k == 2，\(D^1[i][2]\)表示绿色一列，\(D^1[2][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^1[2][j]\)表示的绿色行进行运算并比较更新，获得\(D^2\).

第四步：k == 3，\(D^2[i][3]\)表示绿色一列，\(D^2[3][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^2[3][j]\)表示的绿色行进行运算并比较更新，从而获得\(D^3\).

第五步：k == 4，\(D^3[i][4]\)表示绿色一列，\(D^3[4][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^3[4][j]\)表示的绿色行进行运算并比较更新，从而获得\(D^4\).

第六步：k == 5，\(D^4[i][5]\)表示绿色一列，\(D^4[5][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^3[4][j]\)表示的绿色行进行运算并比较更新，从而获得\(D^5\).

第七步：k == 6，\(D^5[i][6]\)表示绿色一列，\(D^5[6][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^5[6][j]\)表示的绿色行进行运算并比较更新，从而获得\(D^6\).

第八步：k == 7，\(D^6[i][7]\)表示绿色一列，\(D^6[7][j]\)表示绿色的行。0 <=  i <= 8，分别与\(D^6[7][j]\)表示的绿色行进行运算并比较更新，从而获得\(D^7\).

第九步：k == 8，同样的道理进行计算，我们注意到绿色区域划分出的左上角的区域都是不需要被更新的，绿色区域本身也是不更新的，所以\(D^7\)与\(D^8\)是一样的了。

这样，整个弗洛伊德算法的执行过程就结束了，我知道小禹禹看完，可能还是有一点儿模糊，不过我希望你能多看几遍这个例子，最好是自己也和景禹给你们绘制的图一样，自己手工地人脑模拟一遍，只有这样，你才会真正理解算法的精妙所在。

小禹禹也可以对照着上面的分析看如下代码，这样更容易理解。

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] = G.matirx[v][w];
            (*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++ )
            {
                // min([2][3], [2][1] + [1][3])
                if( (*D)[v][w] > (*D)[v][k] + (*D)[k][w] )
                {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];
                }
            }
        }
    }
}

总结

最短路径算法最经典的是迪杰斯特拉算法与弗洛伊德算法，这两个算法也是严蔚敏老师书中所提及的两个算法，当然也有一些其他算法，Bellman-Ford 与 SPFA（Bellman-Ford算法的队列优化）；景禹今后暂时就不更新了，只要大家把迪杰斯特拉算法与弗洛伊德算法掌握了，不论面试考试绝对不在话下。

迪杰斯特拉算法用于计算一个顶点到其他顶点的最短路径的 “单源点” 最短路径算法，弗洛伊德算法用于计算图中任意顶点之间的最短路径的 “ 多源点” 最短路径算法。两者都存在无法处理带负权值图的最短路径算法。但现实情况中也很少存在负权值的情况了，所以还是学好这个算法，哈哈，加油奥！