| 图最短路径算法之弗洛伊德算法（Floyd） | 您所在的位置：网站首页 › warshall-floyd算法在lingo › 图最短路径算法之弗洛伊德算法（Floyd） |
图最短路径算法之弗洛伊德算法（Floyd）
|
Floyd算法
定义概览
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。 Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。 算法描述 1) 算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。 从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在） 从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。 2) 算法描述：a. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 b. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 Floyd算法过程矩阵的计算—-十字交叉法方法：两条线，从左上角开始计算一直到右下角 如下所示 给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点
相应计算方法如下：
核心代码只有 4 行，实在令人赞叹。 private void floyd() { for (int k = 0; k b->c 一定是a到c的最短路c->d->e一定是c到e的最短路，反过来，如果说一条最短路必须要经过点k，那么i->k的最短路加上k->j的最短路一定是i->j 经过k的最短路，因此，最优子结构可以保证。 无后效性状态f[k][i][j]由f[k-1][i][j]，f[k-1][i,k] 以及f[k-1][k][j]转移过来，很容易可以看出，f[k] 的状态完全由f[k-1]转移过来，只要我们把k放倒最外层循环中，就能保证无后效性。 满足以上两个要求，我们即证明了Floyd算法是正确的。 我们最后得出一个状态转移方程：f[k][i][j] = min(f[k-1][i][k],f[k-1][i][k],f[k-1][k][j]) ，可以观察到，这个三维的状态转移方程可以使用滚动数组进行优化。 K 为什么要放在最外层采用动态规划思想，f[k][i][j] 表示 i 和 j 之间可以通过编号为 1…k 的节点的最短路径。 f[0][i][j] 初值为原图的邻接矩阵。 f[k][i][j]则可以从f[k-1][i][j]转移来，表示 i 到 j 不经过 k 这个节点。 也可以 f[k-1][i][k]+f[k-1][k][j] 从转移过来，表示经过 k 这个点。 意思即 f[k][i][j]=min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j]) 然后你就会发现 f 最外层一维空间可以省略，因为 f[k] 只与 f[k-1] 有关。 虽然这个算法非常简单，但也需要找点时间理解这个算法，就不会再有这种问题啦。 Floyd算法的本质是DP，而k是DP的阶段，因此要写最外面。 想象一个图，讨论的是要从1点到达3点，是直接走还是经过中间点2，从而确定两点之间的最短路径。 滚动数组优化滚动数组是一种动态规划中常见的降维优化的方式，应用广泛（背包dp等），可以极大的减少空间复杂度。 在我们求出的状态转移方程中，我们在更新f[k]层状态的时候，用到f[k-1]层的值，f[k-2] f[k-3]层的值就直接废弃了。 所以我们大可让第一层的大小从n变成2,再进一步，我们在f[k]层更新f[k][i][j]的时候，f[k-1][i][k] 和 f[k-1][k][j] 我们如果能保证，在更新k层另外一组路径m->n的时候，不受前面更新过的f[k][i][j]的影响，就可以把第一维度去掉了。 我们现在去掉第一个维度，写成我们在代码中的那样，就是f[i][j] 依赖 f[i][k] + f[k][j] 我们在更新f[m][n]的时候，用到了f[m][k] + f[k][n] 假设f[i][j]的更新影响到了f[m][k] 或者 f[k][m] 即 {m=i,k=j} 或者 {k=i,n=j} 这时候有两种情况，j和k是同一个点，或者i和k是同一个点，那么 f[i][j] = f[i][j] + f[j][j]，或者f[i][j] = f[i][i]+f[i][j] 这时候，我们所谓的“前面更新的点对”还是这两个点本来的路径，也就是说，唯一两种在某一层先更新的点，影响到后更新的点的情况，是完全合理的，所以说，我们即时把第一维去掉，也满足无后效性原则。 因此可以用滚动数组优化。 优化之后的状态转移方程即为：f[i][j] = min(f[i][j],f[i][k]+f[k][j])。 求具体路径：我们上面仅仅是知道了最短路径的长度，实际应用中我们常常是需要知道具体的路径，在Floyd算法中怎么求具体路径呢，很简单，我们只需要记录下来在更新f[i][j]的时候，用到的中间节点是哪个就可以了。 假设我们用path[i][j]记录从i到j松弛的节点k，那么从i到j,肯定是先从i到k，然后再从k到j， 那么我们在找出path[i][k] , path[k][j]即可。 即 i到k的最短路是 i -> path[i][k] -> k -> path[k][j] -> k q` 然后求path[i][k]和path[k][j] ，一直到某两个节点没有中间节点为止，代码如下： 在更新路径的时候： if(a[i][k]>temp){ a[i][j] = temp; path[i][j] = k; }求路径的时候： public String getPath(int[][] path, int i, int j) { if (path[i][j] == -1) { return " "+i+" "+j; } else { int k = path[i][j]; return getPath(path, i, k)+" "+getPath(path, k, j)+" "; } } 总结Floyd算法只能在不存在负权环的情况下使用，因为其并不能判断负权环，上面也说过，如果有负权环，那么最短路将无意义，因为我们可以不断走负权环，这样最短路径值便成为了负无穷。 但是其可以处理带负权边但是无负权环的情况。 以上就是求多源最短路的Floyd算法，基于动态规划，十分优雅。 但是其复杂度确实是不敢恭维，因为要维护一个路径矩阵，因此空间复杂度达到了O(n^2)，时间复杂度达到了O(n^3)，只有在数据规模很小的时候，才适合使用这个算法，但是在实际的应用中，求单源最短路是最常见的，比如在路由算法中，某个节点仅需要知道从这个节点出发到达其他节点的最短路径，而不需要知道其他点的情况，因此在路由算法中最适合的应该是单源最短路算法，Dijkstra算法。 拓展阅读Dijkstra 算法 6 大算法贪心算法 动态规划算法 参考资料 书籍《大话数据结构》 blog知乎-Floyd算法为什么把k放在最外层？ 知乎-算法系列——四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA 知乎-Floyd 算法 CSDN-为什么Floyd算法中k必须放在最外层 cnblogs-最短路径—Dijkstra算法和Floyd算法 数据结构（五）图—最短路径（弗洛伊德算法） Floyd-傻子也能看懂的弗洛伊德算法（转） Floyd算法 定义概览 算法描述 1) 算法思想原理： 2) 算法描述： Floyd算法过程矩阵的计算—-十字交叉法 代码实现 java 版本 正确性分析 K 为什么要放在最外层 滚动数组优化 求具体路径： 总结 拓展阅读 6 大算法 参考资料 书籍 blog 更多学习 个人 Github 个人公众号更多实时资讯，前沿技术，生活趣事。尽在【老马啸西风】 交流社群：[交流群信息](https://mp.weixin.qq.com/s/rkSvXxiiLGjl3S-ZOZCr0Q)
|
【本文地址】