Floyd-Warshall所有点对间最短距离专题

班级：计研-10 姓名：刘妍妍 学号：2010301320132 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的最短路径。 （1）​ 如果不存在，那么之前的计算结果，dist[k-1][i][j]仍然是我们现在的最好结果。 （2）​ 如果存在，这条最短路径就会被分为两条子路：一条从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], if k = 0 min(dist[k-1][i][j], dist[k-1][i][k]+dist[k-1][k][j], if k > 0 易知 dist 的第一维可以省略，从而得到经典代码： for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 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” void allPairShortest(Graph const &graph, /*输入*/ vector> &dist, /*输出*/ vector>&pred){ /*输出*/ int n=graph.numberVertices(); //将对角线上的dist[][]设置为0，如果没有边的话设置为INFINITY, //dist[u][v]的值就是边(u,v)的权值，同样的方法来初始化pred数组。 for(int u=0;u::max()); pred[u].assign(n,-1); dist[u][u]=0; for(VertexList::const_iterator ci=graph.begin(u);ci!=graph.end(u);++ci){ int v=ci->first; dist[u][v]=ci->second; pred[u][v]=u ; } for(int k=0;k::max()){contine;} //如果能够找到一条减少距离的路径，更新dist[][]。 //使用长整型避免溢出。 for(int j=0;j> const &pred, /*输入*/ list &path){ /*输出*/ path.clear(); if(t<0||t>=(int)pred.size()||s<0||s>=(int)pred.size()){ return; } //不断扩展路径，知道我们达到源点s或者得到表示没有路径的-1 。 path.push_front(t); while(t!=s){ t=pred[s][t]; if(t==-1){ path.clear();return; } path.push_front(t); } } 分析：Floyd-Warshall算法的时间主要耗费在最小化函数上，时间为O（V3），我们可以从这三层嵌套循环中看出来。例2中的constructshortestPath函数将会花费O（E）的时间，因为最短路径可能会经过图中的每一条边。 二、算例分析：小城镇消防站选址问题探析 在把小城镇交通网络等效为有向拓扑图的基础上,将各个安全保护点以及消防站等效为有向图上的各个顶点。采用求解最短路问题的Floyd算法对小城镇的消防安全问题进行了分析,从中得出消防站选址方法及发生火灾时的最佳救援路线的选择。 如图表示的是某城区的简明交通网络图，边值是正常交通状况下两点之间的消防车所需花费的时间单位数。火灾发生地位于V2附近，消防站位于V4，要求消防警力在最短时间内到达火灾发生现场，试求其最佳行车路径.可根据算法求出每步后的dist和pred，整合得到易看出每步后的最短距离和路径。 由权矩阵D（5）可知，从顶点v4到v2的最短路程为6，最短路径为：V4-V1-V3-V2. 三、应用进阶 1、传递闭包 把 dist[i][j] = true 视为存在 i 到 j 的路径即可。dist[i, j] = dist[i, j] Or ( dist[i, k] And dist[ k, j] )  2、寻找有向图的最小圈 对 于一个最小圈，它必然存在一个编号最大的顶点，比如为 k，那么在执行 Floydist-Warshall 算法的第 k 次外层迭代前，dist[i][j] 存放的是中间顶点在集合 {1,2,...,k-1} 中，i 到 j 的最短路径。容易知道此时 dist[i][k]+distist[k][j]+A[j][i] 就是最大编号为 k、包含 i、j、k（绕向为 j->i->k）的最小圈。做完 n 次迭代后，我们就可以知道最大编号为任意值的最小圈：最大编号为1的最小圈、最大编号为2的最小圈、……、最大编号为n的最小圈，这些值中取最小值即可。 int best = 0; for (int k = 1; k <= n; ++k) { for (int i = 1; i <= k; ++i) for (int j = 1; j <= k; ++j) if (dist[i][k]+dist[k][j]+A[j][i] < best) best = dist[i][k]+dist[k][j]+A[j][i]; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (dist[i][k]+dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k]+dist[k][j]; } 3、Fence Loops 题目大意：给定一个无向图 G，求出 G 的最小圈。输入方式比较怪异，给出的是与某条边一端相连的边的序号。 分 析：设 w[i] 为边 i 的权值，A[i][j] = w[i]+w[j]，以此为邻接矩阵。那么对于最小圈 e1 -> e2 -> ... -> em -> e1，我们求出的值是 A[1][2]+A[2][3]+...+A[m-1][m]+A[m][1]，也就是 2(w[1]+w[2]+...+w[m])。 4、Cow Toll Paths 题目大意，给定点边均赋权的无向图，顶点数 N <= 250，边数 M <= 10000，有 K <= 10000 个询问，询问 u 到 v 的最小花费。花费定义为一条路经上所有边的权值和，加上路径上顶点中的最大权值。 分析：w[i] 为顶点 i 的权值。枚举顶点 p，只允许经过权值小于 w[p] 的顶点，用任一最短路径算法求出 u 到 v 的最短路径，加上 w[p] 即为总花费。取最小值即可。 其实可以利用 Floyd-Warshall 的性质，把顶点按权值从小到大排序，以此对顶点重编号。可知第 k(u,v <= k) 次外层迭代后，dist[u][v] + w[k] 就是以 k 为最大权值顶点的最小花费。