解决方案

动态规划方法将会依序计算distk[i][j],0≤k≤n,得到经过顶点v1,v2,……,vk的从vi到vj的最短路径,distk[i][j][1]。例如,当k=0时,dist0[i][j]将会是边(i,j)的权值,如果不存在这样一条边的话,那么值为∞。当k=1时,我们将会检查所有的i和j,是否存在两条边(vi,v1)和(v1,vj),其和小于边(vi,vj)。如果我们继续这个逻辑,直到k=n,这时我们得到vi到vj的最终最短路径。

对于k>0,我们假设计算distk时,distk-1已经被计算出来(在动态规划中,我们需要以一种正确的方法解决这些子问题)。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

Floyd-Warshall从k=0开始进行处理,直到k=n,即distn[][]被计算出来。在计算distk[i][j]时,我们需要知道是否存在一条通过vk的从vi到vj的最短路径。

·如果不存在,那么之前的计算结果,distk-1[i][j]仍然是我们现在的最好结果。

·如果存在,这条最短路径就会被分成两条子路:一条从vi到vk的最短路径,长度为distk-1[i][k],加上一条从vk到vj的最短路径,长度为distk-1[k][j]。从vi到vj的最短路径将会是distk-1[i][k]+distk-1[k][j]。

我们将不会尝试着分辨这两种情况,我们将会计算这两个值,然后取最小的那个。当第二种情况的值较小时,Floyd-Warshall发现了一条更短的路径。看起来也许很惊讶,因为我们不需要记录这条路径是什么。而且更惊讶的是,我们只需要一个矩阵dist,而不是n+1个矩阵。因为我们只关心总距离,而不是关心经过最少顶点的路径。例6-7给出了这个令人惊讶的解决方案。

例6-7:计算所有点对最短路径的Floyd-Warshall算法

阅读 ‧ 电子书库
阅读 ‧ 电子书库

Floyd-Warshall计算出dist[i][j],即在有向有权图中从vi到vj的最短路径,按照这个方法,我们能够计算出pred矩阵,来得到两个顶点之间的实际最短路径。例6-8中的那个简单的函数得到了一条从vs到vt的实际的最短路径(也许有更多)。这个函数根据pred矩阵中的数据来构建出最短路径。

例6-8:从已知的pred[][]构建出最短路径代码

阅读 ‧ 电子书库
[1]这些顶点并不需要区分开;也就是说,i可能等于j或者1≤i≤k或者1≤j≤k。