《C++入门到入土》——最短路径（全集）

提醒：本篇含有Floyd、Dijkstra及其堆优化和优先队列优化、Bellman-Ford、死了的SPFA，篇幅较长，请选取需要观看（以上为本篇介绍顺序）

注：除Floyd和Bellman-Ford外其余算法使用vector邻接表存图，m表示图的边数，n表示图的节点数

前置定义：

• 最短路径指在一张有权图中，从一个节点到达另一个节点经过的边的权值总和最小的路径，最常见为单源最短路径，即求从一个给定点分别到其他所有节点的最短路径

• 松弛操作指通过第三点减小两点之间的距离

• 稀疏图指m远小于n^2或接近n的图，稠密图指m接近n^2的图，一个图的边越多越稠密

这里先用P3371（单源最短路径不卡SPFA版弱化版）做例题：

首先介绍最暴力 最简洁 最好懂的：

Floyd（江湖人称“五行算法”（核心真的只有五行（甚至四行）））

Floyd基于贪心的算法，思想是依次枚举三个节点，看能否通过第三个节点进行松弛，而这也注定了它O(n^3)的时间复杂度和O(n^2)的空间复杂度在绝大多数场所行不通，但它的优势就是可以同时实现多源最短路径（求任意两节点间最短路径）

核心代码：

a[ i ][ j ]表示节点 i 到 j 的最短距离，根据需要输出就行了

Floyd虽然简单好想，但三个for循环毕竟是个问题（想不TLE都难），于是便引出了我们最常用、最泛用、最不易被卡的最短路算法：

Dijkstra（贪心万岁！）

Dij基于贪心，每次所有点中选出一个未被选中过的点 t ，使得点 t 到起点 s 的距离最小，再通过点 t 将其他顶点松弛。

根据这样的操作，我们可以保证每次选中的点 t 不可能再被松弛：我们令dis[ i ]为 i 到起点 s 的已知最短距离，若节点 t 已经被选中过，说明dis[ t ]一定小于dis[ now ]（now为当前选中进行松弛操作的节点），不然 now 应该比 t 先被选中。所以一个节点被选中后，说明其dis值已经确定，不会在进行更改。因此最多有 n-1 个节点被选中，每次寻找点 t 时时间最多为O(n)，进行松弛操作总时间为O(n+m)这样总时间复杂度最多就是O(n^2+(n+m) )=O(n^2)，比Floyd稍好。

核心代码：

可这种算法的时间复杂度还是有些高，O(n^2）足以被绝大多数题目卡掉，还有没有更快的方法呢？

我们注意，松弛操作肯定是没法优化了，遍历边的时间复杂度降不下去。但上述代码中寻找距离起点最近的点 t 时每次都需要扫过n个点，那能不能从这里下手呢？

在数据结构中维护一个最大值……这不就是……

堆！

我们只需要把需要的节点和它的dis值存入一个堆中，然后以dis值为关键词维护最小堆，需要时再弹出堆顶元素进行松弛不就行了？

我们发现，如果一个节点 t 可能成为被选中进行松弛操作的节点，t 的dis值一定是被更新过的（若不被更新，则其子节点 k 仍满足dis[ k ]<=dis[ t ]+ t 与 k 之间的距离 ，只有dis[ t ]改变才可能打破这个不等关系将 k 松弛），并且这个节点的dis值也就确定了（证明很好想，这个节点 t 的dis值既然已经是目前最小的了，若还能被其他节点 k 松弛，说明dis[ t ]>dis[ k ]+从t到k的距离，也就是说dis[ k ]<dis[ t ]，与假设相矛盾）。

因此我们只需要在每次进行松弛操作时将那些成功被松弛的节点放入堆中即可。若堆中已经存在该节点，就将该节点在堆中的dis值更新，再进行相应的维护。

我们知道，存在n次弹出堆顶，m次插入；堆中最多存在n个元素，维护堆的时间复杂度是O(log n)，这样一来时间就优化成了O( (n+m) log n )=O( m log n )。

核心代码：

哪有什么核心代码？手打堆所有代码都是核心！

手打堆的代码肉眼可见的变得非常多，那有没有时间差不多但代码简单的呢？

（我都这么说了那肯定有啊）

在这里，我们要隆重请出我们的STL模板：

priority_queue（优先队列）

优先队列的本质是一个堆，优先队列的top就是队列中的最大/最小值（最大堆和最小堆需要自己定义）。优先队列不仅能存普通的int、long long，也可以存结构体，但在结构体中我们需要进行重载运算符才能维护堆。

我们知道，只有dis值被更新的节点才可能被下一次选中，因此我们需要在每次更新 t 的dis值时将 t 和dis一起放入优先队列中。但注意：同一节点 t 可能被更新过多次dis值，因此优先队列中可能存在多个 t 与其dis值，而这些无用的数据只能保留在优先队列中，因此优先队列中的元素个数最多为m个，这样维护优先队列的时间就降低到了O（log m），其他的时间复杂度相同，总时间复杂度为O（m log m），比堆优化略差

但它简单啊

核心代码：

至此，Dijkstra及其优化看似很完美了实际上也很完美了，但它有一个致命的缺点：

不能解决带有负权边的问题

举个图例就知道了：

在这个图中，我们如果按照先前的思路，应该最先选中3这个节点并将其dis值确定为2，可我们如果通过1->2->3的路径走，会发现3的dis值应该为1，这就是贪心算法在解决含有负权边时的弊端。

而下面介绍的这种算法，则解决了这种问题：

Bellman-Ford（死了一半）

这种算法的思想是每次都枚举m条边，看能否松弛某几条边。

在第一轮松弛后，我们可以得到起点最多经过一条边到达其余节点的最短距离；第二轮松弛后，就可以得到最多经过两条边到达其余节点的最短距离。而一个节点到另一个节点的最短路径最多需要经过 n-1 条边，这样就最多需要 n-1 轮枚举，每次枚举 m 条边，时间复杂度是O（nm）

核心代码：

将上图的负权边代入，会发现3号节点的dis值最后被松弛为了1，也就是说该算法可以解决含有负权边的问题。

但是O（nm）的时间复杂度摆在那里，在m=n^2时最坏能卡成和Floyd一样的O（n^3），所以我们也需要用些优（xuan）美（xue）的方法来优化它。

我们注意，同样，只有一个节点被松弛过，那么与它相连的节点才可能在下一轮被松弛。因此我们可以同样使用一个队列（注意：不需要优先队列，这个只是记录顺序），将该轮被松弛过的节点放入队列中，并且队列中不可以同时存在两个相同的节点（同一轮只对一个节点进行一次松弛），我们可以用一个数组判重。

这种使用队列优化的Bellman-Ford算法，江湖人称：

死了的SPFA（考场慎用）（但是能帮你判断负环）

没错，死了的SPFA说的正是它。因为即使使用了队列优化，也可以轻松被普（du）通（liu）数据卡回O（nm）的原型，所以只要没有负权边，能用Diikstra就不要考虑SPFA的事情了。

核心代码：

还记得么？我刚才提到了一个词：负环。负环指的是一个边权和小于0的环，如果一个图存在负环，那么图就不会存在最短路，因为每走一次负环最短路径距离就会减少，我们可以通过这个负环进行无数次松弛。而SPFA有一个独特的方法判断负环：

我们已知，若不存在负环，Bellman-Ford算法最多进行 n-1 次扫描所有边的操作，也就是一个点最多被松弛 n-1 次；在SPFA中，若一个点入队的次数达到了n，就说明该点被松弛了n次。而理论上一个点最多只存在n-1次松弛操作，也就是说，此时图内含有负环，使得该节点可以一直更新dis值。我们只需要再加一个数组，存放节点入队的次数就行了

核心代码：

那么以上就是所有基础最短路算法了，这可以说是图中最重要的一类算法，有许多问题都可以转化为最短路问题求解。

完结撒xck~

祈愿流浪者啊啊啊！