Floyd-Warshall算法解决所有点对间的最短路径.docx

Floyd-Warshall算法解决所有点对间的最短路径
Floyd-Warshall可以比较高效地解决图论中多源最短路径的问题。它的本质是一次标号法动态规划——正因为如此，这个算法的实现有了非常难能可贵的一点，那就是它的简洁。所以很多人在求单源短路的时候都会用它，而不是效率更高但实现略烦的Dijkstra或者Bellman-Ford（当然是在时间比较宽裕的时候）。

Floyd-Warshall算法是有向图（当前也适用于无向图）中求最短路径长度的算法，可以得到各对点间的最短路径，并且允许存在负权值的边，时间复杂度Θ(|V|^3)。

一、算法
输入：
一个有向权图G=（V，E）。每条边的权值e=（u,v）。图G的顶点个数为n。

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

解决方案：
动态规划方法将会依次计算dist[k][i][j],0<=k<=n,得到经过顶点v1，v2，…，vk的从vi到vj的最短路径，dist[k][i][j]。例如，当k=0时，dist[0][i][j]将会是边（i，j）的权值，如果不存在这样的一条边的话，那么值为∞.当k=1时，我们将会检查所有的i和j，是否存在两条边（vi，v1）和（v1，vj）,其和小于边（vi,vj）。如果我们继续这个逻辑，直到k=n，这时我们得到vi到vj的最终最短路径。
对于k>0，我们假设计算dist[k]时，dist[k-1]已经计算出来（在动态规划和中，我们需要以一种正确的方法解决这些子问题）。
Floyd-Warshall从k=0开始进行处理，直到k=n,即dist[n][][]被计算出来。在计算dist[k][i][j]时，我们需要知道是否存在一条通过vk的从vi到vj的最短路径。
如果不存在，那么之前的计算结果，dist[k-1][i][j]仍然是我们现在的最好结果。
如果存在，这条最短路径就会被分为两条子路：一条从vi到vk的最短路径，长度为dist[k-1][i][k],加上一条从vk到vj的最短路径长度为dist[k-1][k][j]。从vi到vj的最短路径将会是dist[k-1][i][k]+dist[k-1][k][j]。
我们将不会尝试着分辨这两种情况，我们将会计算这两个值，然后取最小的那个。当第二种的情况的值较小时，Floyd-Warshall发现了一条更短的路径。

从而得到dist[k][i][j]的递推式：
dist[k][i][j]=A[i][j],ifk=0
min(dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j],ifk>0
易知dist的第一维可以省略，从而得到经典代码：
for(intk=1;k<=n;++k)
for(inti=1;i<=n;++i)
for(intj=1;j<=n;++j)
if(dist[i][k]+dist[k][j]<dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];

例1：计算所有点对最短路径的Floyd-Warshall算法
#include“Graph.h”
voidallPairShortest(Graphconst&graph,/*输入*/
vector<vector<int>>&dist,/*输出*/
vector<vector<int>>&pred){/*输出*/
intn=graph.numberVertices();
//将对角线上的dist[][]设置为0，如果没有边的话设置为INFINITY,
//dist[u][v]的值就是边(u,v)的权值，同样的方法来初始化pred数组。
for(intu=0;u<n;u++){
dist[u].assign(n,numberic_limits<int>::max());
pred[u].assign(n,-1);
dist[u][u]=0;
for(VertexList::const_iteratorci=graph.begin(u);ci!=graph.end(u);++ci){
intv=ci->first;
dist[u][v]=ci->second;
pred[u][v]=u;
}
for(intk=0;k<n;k++){
for(inti=0;i<n;i++){
if(dist[i][k]==numric_limits<int>::max()){contine;}

//如果能够找到一条减少距离的