单源最短路径相关算法总结

港控/mmm° 2022-09-15 12:54 226阅读 0赞

**1. 单源最短路的简单应用：**

单源最短路径算法主要分为两大类：**有负权边**和**没有负权边**；对于边权非负的可以使用朴素版本的Dijkstra算法和堆优化版本的Dijkstra算法，有负权边的时候可以使用Bellman-Ford算法和spfa算法；朴素版本的Dijkstra算法的时间复杂度为O（n ^ 2），适用于图比较稠密的情况，堆优化版本的Dijkstra算法时间复杂度为O（mlogn），适用于图比较稀疏的情况，spfa算法的时间复杂度为O（km），最坏情况下退化为O（nm），所以有的时候会卡spfa的数据，如果题目卡数据可以换Dijkstra算法（前提是边权非负），spfa不能够解决存在负权回路的图，因为当有负权回路的时候会一直将更新的点存储到队列中造成死循环了，其中n为图中点的个数，m为边的数目；在时间复杂度允许的前提下选择一种自己熟悉的算法解决即可。对于**边权为1的图可以直接使用bfs**来解决（最先到达的点肯定是最近的点，所以最早到达终点的肯定是最短路径）：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

对于图论的问题，一般题目的背景都是比较复杂的，难点在于如何将具体的模型转化为图论的模型，考察的是抽象为具体模型的能力，当我们将问题转化为图论的基本模型之后就可以直接使用模板默写代码了。对于没有负权边的情况，每个点在vis标记数组中只能被更新一次，也即是不可逆的，当这个点被更新之后后面就不再更新了，这也很容易理解，因为求解的是最短路径所以每一次经过的边数越多那么结果是越大的。而存在负权边的时候就不一样了，因为有可能某个点加上了负数之后使得距离更短了，那么以这个点为中间点又可以更新其他的邻接点，而之前某些点是作为最短距离更新过其他点的这个时候也需要被更新，所以这个过程是可逆的，也即每一个点在vis数组中可能被标记几次，也可能进队几次。总的来说dijkstra算法每一个点只会被标记或者入队一次，而spfa则可能出现多次入队的情况，对于dijkstra算法来说是是可以保证拓扑序的，而spfa则不可以保证拓扑序列，有的时候满足拓扑序可以避免很多乱七八糟的问题，

**2. 单源最短路的综合应用**

主要是结合一下其他算法的应用，比如与dfs，二分查找，dp，拓扑排序的结合。

**3. 单元最短路径的扩展应用**

主要是分层图，拆点（分层图），统计路径的条数，次短路的求解。拆点的过程其实是一个dp的过程。最短路径与dp的结合（拆点）：一般在分析问题的时候可以使用dp问题的分析方式，但是在解决问题的时候可以使用最短路径来解决，可以到达的位置我们就可以从上一个位置到当前的这个位置连一条边。对于dp问题的状态计算主要有两种方式：① 当前的状态可以由哪些状态转移过来；② 当前状态可以更新哪些状态；对于最短路径问题来说最常用的是第二种，使用当前的状态去更新其他的状态。dp问题其实与最短路径问题其实有很大的交集，一般来说dp问题使用循环的方式来求解，能够使用循环来求解的一个前提是状态之间没有依赖关系，状态之间不存在环，也即状态之间满足拓扑序，将当前的状态划分为若干个子集之后那么这些子集都是可以直接计算出结果的，那么就就可以根据划分的子集计算出当前状态的dp中，所以使用循环的方式来可以解决满足拓扑序的dp问题，对于不满足拓扑序的dp问题是无法使用循环的方式来求解的，需要将dp问题转换为最短路径问题来求解，最短路径在求解的时候其实是可以避免环的问题，所以可以解决状态之间的依赖关系。dp问题转化为最短路径问题之后就需要建图，需要将当前状态可以到达的状态连上一条边，然后使用最短路径算法。比较典型的关于拆点和拓扑图的题目有[1131 拯救大兵瑞恩][1131]，1134最短路计数

**4. 求最短路路径的算法**

主要有三大类，分别为：① bfs ② dijkstra算法 ③ Bellman-ford或者是spfa算法；dijkstra算法基于贪心的思想，Bellman-ford/spfa算法基于dp思想，floyd算法也是基于dp的思想

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2c29cc90fff846e6bd7452f9c64f375a.png
[1131]: https://blog.csdn.net/qq_39445165/article/details/120871287