算法导论 25.2 Floyed-Warshall算法

一，Floyed-Warshall算法的思想

        Floyed-Warshall算法（以下简称FW）用一种不同的动态规划公式来解决所有结点对的最短路径问题，有向图的权值可以为负，但不能存在负值环路。与25.1中的方法不同的是，25.1中是通过每次拓展一条边，而FW算法则是用已知最短路径的(i,k)和(k,j)的值来算出(i,j)的最短路径。

二，FW算法的递归定义

        若k=0，dij(k)=wij；若k>=1，dij(k)=min(dij(k-1),dik(k-1)+dkj(k-1))；也就是说，D(0)=W，第k个最短路径权重矩阵D(k)的每个元素应该是D(k-1)对应元素的值与D(k-1)中i到k的最短路径加上k到j的最短路径中的最小值。

三，FW算法的伪代码

FLOYD-WARSHALL(W)

1. n=W.rows

2. D(0)=W

3. for k=1 to n

4.     letD(k)=(dij(k))be a new n*n matrix

5.     for i=1 to n

6.         for j=1 to n

7.             dij(k)=min(dij(k-1),dik(k-1)+dkj(k-1))

8. return D(n)

第1-2行中，令n等于初始矩阵W的行数，并构建了一个最短路径权重矩阵D，让它初始为W；第3-7行中，有三个循环，k循环从1到n，表示对D(1)到D(n)共n个矩阵的遍历，内层的两个循环遍历矩阵D(k)的每个元素，让其满足递归定义；第8行返回最终矩阵D(n)

以书上的例子为例，D(0)和π(0)都是根据图的初始矩阵，因为有5个结点，所以我们需要计算5次矩阵，D(1)中k=1，我们计算一下从i到j是否经过1这个结点，发现4到2,4到3,4到5会经过结点1，计算一下4到1的最短路径+1到2和1到3、5的最短路径，我们发现4到2的最短路径需要更新为5，4到5的最短路径更新为-2，而4到3的最短路径原来是-5，比刚刚计算出来的10要小，所以不更新；D(2)中k=2，同理我们找到经过2的i和j，找到1到4,1到5,3到4,3到5，4到5，计算结果为4、10、5、11、8，更新d14=4，d34=5,，d35=11；D(3)到D(5)同理进行更新，得到最后的最短路径权重图D(5)

四，FW算法的复杂度

时间复杂度：三个循环所耗时间为O(n³)