Yan`s Notepad

--- My Notepad......Articles, tools and etc.
Floyd算法几行间的理解
Floyd-Warshall算法也就是所谓的弗洛伊德算法是一种经典而又简洁的多源最短路径算法。整个算法有效的部分不过4行。事实上,应付而言,背下来都可。
#ifndef min                            // 定义最小值min, 似乎...某些地方没有它
#define min(a, b)     ((a) < (b) ? (a) : (b))
#endif
int i, j, k;
for (k = 0; k < BUFF_W; k++)           // 以每一个节点作为中转
{
    for (i = 0; i < BUFF_W; i++)       // 遍历整个邻接矩阵
        for (j = 0; j < BUFF_H; j++)   // 在i->j和i->k,k->j中找到最短的一个路径
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
}
但是我们要问为什么才是。简洁的程序似乎正在暗示我们它是一个动态规划过程。我们先抛开这些看着头晕的式子,直接考虑一下,这个图和它的邻接矩阵:
···图片正在加载···
images/floydAlogrithm/graph_0.png
一个有向加权图
图中为了方便起见,为邻接矩阵标上了行和列。
我们先考虑少数的顶点,顶点1,5,4,很显然,1 -> 4的最短路径是它本身,而不是经过5中转(1 -> 5, 5 -> 4);此时,A(1,4)的值设置为9,而不是19(因为最短路径是9,不是19)。此时,邻接矩阵没有变动,因为A(1,4)本身就是9.
现在,考虑顶点1,5,4,3,一样的,1 -> 3有两种情况:一种是1 -> 3,一种是1 -> 4 -> 3;为什么不是1 -> 5 -> 4 -> 3呢?因为之前的一步已经计算出了1 -> 4的最短路径是1 -> 4这条,而不是1 -> 5 -> 4,那么自然的,1 -> 3肯定是要先找最短的走——而不是选择绕道而行。如此一来,A(1, 3)就会被修改为14了(1 -> 4的权值为9,4 -> 3的长度为5,9 + 5 = 14)。这样的话,邻接矩阵就会发生一个变动:
···图片正在加载···
images/floydAlogrithm/graph_1.png
变动之后
这样,这两步的思路应该很清晰了——先以顶点5作为中转,找到1 -> 4的最短距离,然后以顶点4作为中转,找到1 -> 3的最短距离。注意顺序,我们先用顶点5作为中转,然后找到了1 -> 4的最短路径——换句话说,以顶点5为中转,应该也去找1 -> 5, 1 -> 3, 2 -> 3...等等各个顶点间的最短路径,然后完成后,再以其它的顶点(本例中是顶点4)为中转,继续查找各个顶点间的最短路径
返回来考虑1 -> 4的最短路径问题,这次找到一般情况。
很明显,它可以用5中转,也可以是2,3,甚至是本身(因为本身到本身的权值为0,这并没有什么用)。换句话说,针对于顶点a -> b的最短路径,可能是a -> b,也可能是a -> k, k -> b,其中的k可以是这个图里的任何一个顶点。在其中取得最小值,就是a -> b的最短路径。
将这句话放到邻接矩阵中,就变成了:对于i -> j,k是其中的每一个顶点,i -> k的最短路径要么是i -> j,要么是 i -> k + k -> j。又因为我们之前提到的顺序问题,因此,最外层我们尝试每一个顶点k,内层对于图中每一条边i -> j都进行上述的测试,整个程序运行完后,邻接矩阵中留下的就是i -> j的最短路径了。对应于篇首的代码,应该是可以很清晰的明白为什么三层循环那样潜嵌套,为什么min里面那样写。如果我们用数学化的式子把它写出来,那么该算法的这个递推过程就是:
small