『算法-ACM 竞赛-图论-最短路』 关于 SPFA Bellman-Ford Dijkstra Floyd BFS 最短路的共同点与区别

关于 SPFA Bellman-Ford Dijkstra Floyd BFS 最短路的共同点与区别

关于模板什么的还有算法的具体介绍 戳我 这里我们只做所有最短路的具体分析。

那么同是求解最短路，这些算法到底有什么区别和联系：

对于 BFS 来说，他没有松弛操作，他的理论思想是从每一点做树形便利，那么时间复杂度绝对是在大型图中难以接受的，所以 BFS 题目设计很精巧，数据限制，更重要的是他可以处理一些条件很麻烦的联通情况，比如在途中，每步长相同求到达某一地的时间，那么我们要用最短路，就需要建图，但是借助 BFS 就不需要建图，这么麻烦的事情了。

对于其他最短路，核心思想是松弛，那么先说 Floyd，其核心思想是插点法松弛借助动态规划，这就是重点，那么既然是插点而且是动态规划，那么他就可以解决过某一点的最短最长路，或最什么什么的问题了，因为 DP 会不重复的枚举每一种情况，相当于插了尽可能的点，那么插点的问题就可以解决，比如不经过某一点的最短路问题，不经过超得过某个值的点的最短路。

对于最短路的其他算法，先讨论 Ford 家族，Bellman-Ford 与 SPFA 的区别，emmm，名字不一样，速度不一样，但是使用情况都一样，都是可处理负边权，但是复杂度最恶劣为 O（VE) 顶点数乘边数，那么稠密图直接挂掉。都能能判负环，Bellman 是 n-1 次松弛之后如果还能松弛，那么就有负环，SPFA 是若同一点进入队列两次，即为存在负环。Bellman 时间复杂度为 O（VE） SPFA(队列优化的 Bellman ford）复杂度为 O(KE) K 为常数约为 3，但是稠密图会退化到 O（VE）上面说了。

再说 dijkstra，这个算法最快，稠密图稀疏图都可使用，也有一个队列优化版，区别参考上文，这个算法因为本身设计的问题是不可以处理负边权问题的，所以更不能处理负环，但他不会退化，这里我们比较晚异同，我们给出求解思路。

确定为单源最短路：这里是说如果是多源最短路，那么跑 N 边最短路也比 Floyd 快，也算是单源最短路。

1.判断是否为稠密图

① 是：判断是否带负边权：有还是 Ford 算法，两个都可以，但是 SPFA 用的多，用它；

② 否：SPFA；

多源最短路，或者就是 Floyd 算法的特殊问题。

Floyd ；

那么板子就可以只背 3 个了。