首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》所有点对最短路径

关灯直达底部

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

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

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

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

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

图 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)。

[1]可能有多条有相同长度的路径。