弗洛伊德算法学习笔记
Floyd算法学习笔记(未完结)
前言
如有错误，欢迎大劳批评指出。
前置芝士：
1.邻接矩阵(弗洛伊德想用邻接矩阵保存图形)
2.动态规划的思路(最好学一学，没学的话影响不大)
1. Floyd 所解决问题的类型
我们可以发现，诸如Dijkstra、SPFA、Bellman Ford等最短路径算法都解决了单源点的最短路径问题，即确定起点或终点来寻找最短路径问题。然而，我们发现这些算法效率太低，无法解决具有多个源的最短路径问题，即具有多个起点和终点的最短路径问题。假设有\(n\)个点和\(m\)条边。在求解多源最短路径时，如果用上述三种算法求解，则需要分别做\(n\)次才能从每个点开始求解单源最短路径。最慢的时间复杂度是\ (o (nlogm)，o (n 2m)，o (n 2m) \)，在稠密图中\ (m=n)因此，我们今天的主角Floyd就是为了解决多源最短路径问题而诞生的！
2. Floyd 的思想和基本做法
弗洛伊德算法的基本思想是动态规划。
让\(dp_{ij}\)代表从\(i\)到\(j\)的最短距离。(有\(n\)个点)
首先，这个\(dp\)数组的初始化是将输入边\(x-y\)的权重设置为\(z\)(加权图为\(1\))，如果图是无向图，那么\(dp_{xy}=dp_{yx}=z\)
然后我们进行状态转换。显然，如果我们想转移\(dp_{ij}\)，我们需要找到一个点\(k\)来转移，那就是\ (DP _ {ij} \ getsmin (DP _ {ij}，DP _ {ik} DP _ {kj}) \)
这里需要注意的是，我们的\(k\)层循环必须放在\(i\)和\(j\)层循环之外，因为如果放在\(i，j\)内，你会发现每两点的最短路径只会被计数一次，当你处于状态转换时，你只
Floyd算法的时间复杂度为\(o(n ^ 3)\)，因为\(i，j，k\)必须枚举一层循环，比前三种算法快。
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/100417.html