阅读 ‧ 电子书库

所有点对最短路径

我们通常不是寻找单源最短路径^[1]，而是在任意两个顶点（v_i,v_j）之间寻找最短路径。最快解决这个问题的方法是使用一个强有力的方法——动态规划。

动态规划有两个令人激动的特征：

·它专注解决较小的，有条件限制的问题。当限制条件很严格时，函数将会非常简单，系统地松弛限制条件，直到最后产生希望得到的结果。

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

·虽然我们希望为问题寻找到最优解，计算最优解的值比寻找什么是最优解要简单许多。在我们的例子中，计算每个点对（v_i,v_j）之间的最短距离，然后进行一些额外的计算得到实际的路径。

给定一个n×n的dist矩阵，我们计算得到，对于所有的顶点对（v_i,v_j）来说，dist[i][j]是v_i到v_j的最短路径。图6-18是Floyd-Warshall的伪代码，以及它在一个小例子上的执行过程。

输入/输出

输入

一个有向有权图G=(V,E)。每条边e=(u,v)都有一个正权值。图G的顶点数为n。

输出

Floyd-Warshall算法得到一个矩阵dist[][]，dist[u][v]的值表示从u到b的最短路径。注意如果dist[u][v]是∞，那么从u到v之间不存在路径。在两个顶点之间的实际路径可以从矩阵pred[][]推导出来，当然，pred[][]也是这个算法计算的结果。

假设

边的权值必须为正值（例如必须大于0）。