说说弗洛伊德算法

2015/2/1 posted in  算法&数据结构

弗洛伊德算法,是当时集训的时候学最短路问题的第一个算法(去年寒假),当时学长直说这个算法好写、时间复杂度高,至于这个算法是什么原理却没有讲。学长说,照着敲就可以,循环敲对了,就那么神奇的对了,循环顺序错了,就神奇的WA了。

今年寒假,我也是学长了,逗比硕把最短路给我了,就变成这一周我要讲搜索和最短路。

搜索有BFS和DFS两个算法,或者说是思想,而最短路有4个算法。开始重点看搜索和最短路,翻来覆去好几遍。然后对搜索和走最短路的各个算法都有了进一步的理解,对这几种东西不再仅仅是限于会用模板了。

在与学弟的交流并解决学弟的疑问的同时,也让我看到的搜索和最短路那些只抄模板很容易忽略的地方。其实和学弟交流也能让自己发现并学到之前自己没有注意到的东西。

好了,主要说弗洛伊德的思想。之前最短路的总结就写过弗洛伊德。但没有解释弗洛伊德,这篇文章主要解释弗洛伊德原理。

摆出弗洛伊德的代码:

int fld (int n,int s,int e)
{
    int d[200][200];
    int i,j,k;
    memcpy(d,G,sizeof (G));

    for (k = 1;k <= n;k++)
        for (i = 1;i <= n;i++)
            for (j = 1;j <= n;j++)
                d[i][j] = qmin (d[i][j],d[i][k] + d[k][j]);

    return d[s][e];
}

首先,要明确,弗洛伊德是求任意两点之间的最短路。而他记录任意两点之间的距离是靠一个二维数组实现的。

然后说弗洛伊德是怎么实现的。

开始的时候,有个d数组(见上方代码),开始的时候是复制的G(一个邻接矩阵),我们可以认为,这个d开始的时候是两个点之间相连的距离。

换句话说,就是如果两个点有相连的边,就有距离,否则就是正无穷。

然后进入循环,从k = 1开始,也就是从1号点开始,对于任意两个点做一个尝试:能不能把1号点放入他们中间。

那么d数组就不是之前的d数组了,现在的d数组可以理解为任意两点之间中间点不超过1个的最短路。

为什么是不超过一个呢?因为刚才把1号点尝试放入任意两个点中间,有的发现如果放入就会更新最短路,换句话说,如果A到B的距离大于A到C然后到B的距离,那么,这个C点就可以放入最短路。与此相同,如果有的可以放入1号点,有的放入对最短路没有改善,那么d数组就是存储的任意两个点之间的最短路。

然后循环继续k = 2,那么,又开始在任意两个点之间尝试吧2号点放入最短路,依然是,有的可以,有的不可以。但是,因为刚才d数组已经不是开始的d数组了,开始的d数组是任意两个点直接相连的最短路,现在的是不超过1个点的最短路。而尝试把2号点放入则会让d数组变成任意两个点的中间点不超过2的最短路。

以此类推,知道把所有点循环完,就认为d数组是存储的任意两个点之间中间点不超过n个点的最短路,实际上,这时候的d已经是站在全局上考虑的d了,而且对于一个n个点的图来说,他的最短路的中间点一定小于n,那么我们就认为,这时候的任意两个点的最短路就是实际上要求的任意两个点的最短路。

算法的魅力不在于用这个算法A掉了一个或更多的题目,而是这个算法本身!