我的无优化 SPFA 果然有问题

SPFA 是一个非常好用的最短路径算法，可以跑负边权、判负环。但总有一些良心出题人要卡掉它。

我是 SPFA 小姐的狗！

前置知识

先复习一下，不然大家可能已经忘记算法原理了。

Bellman–Ford 算法：不断尝试对图上每条边进行松弛。每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

假设最短路存在，那么一次松弛操作会使得最短路的边数至少加 \(1\)。又因为最短路的边数最多为 \(n-1\)，那么最多执行 \(n-1\) 轮松弛操作，总时间复杂度为 \(O(nm)\)。

Bellman–Ford 算法显然是会遍历很多没有必要再去遍历的边，所以它的复杂度不优。

显然，只有上一次被松弛的点所连接的边才有可能被松弛，那么我们就可以把被松弛的点放入队列，只去遍历队列中的点所连的边，这就是 SPFA 算法的原理。

显然，它的时间复杂度是 \(O(kE)\)，\(E\) 为边数，\(k\) 为每个点平均入队次数，一般有 \(k \leq 2\)。

简单优化

1. SLF 优化（Small Label First）

把普通的队列变成双端队列，对于即将入队的元素 \(x\)，将其与队首元素的 \(\operatorname{dis}_x\) 进行比较，若队首元素较大，则从队首插入；否则从队尾插入。

2. LLL 优化（Large Label Last）

也是使用双端队列，维护当前队列中元素到起点距离的平均值，设这个平均值为 \(ave\)，若 \(\operatorname{dis}_x>ave\)，从队尾插入；否则从队首插入。

意义：可以让更新出结点最终解可能性更大的结点优先进行更新，减少了迭代次数。

较高级优化

1. SLF 优化带容错

定义一个容错值 \(diff\)，当 \(\operatorname{dis}_x\) 大于队首元素的 \(\operatorname{dis}+diff\) 时，从队尾插入；否则从队首插入。

意义：可以使程序不陷入局部最优解。

2. mcfx 优化

定义一个区间 \(\left[ l,r \right]\)（通常取 \(l = 2,r=\sqrt{V}\)），当入队结点的入队次数属于这个区间时，从队首插入；否则从队尾插入。

意义：网格图表现优秀。假设有一个结点，从这个结点出发的大多数边都只能更新一个非最优解，那么它会导致迭代过多，那么经过 mcfx 优化可以使得它在队列中的优先级降低。一般可以与带容错的 SLF 优化一同使用。

3. Swap-SLF

若队列发生改变，并且有队首元素的 \(\operatorname{dis}\) 大于队尾元素的 \(\operatorname{dis}\)，那么交换队首和队尾元素。

意义：比普通的 SLF 优化快很多，可以让队列更加接近优先队列，非常难卡。

4. 基于 DFS 的优化

原本的 SPFA 算法使用广度优先搜索，对于扩展的新结点，总是放到队列末尾，这样会中断迭代的连续性。那我们采用深度优先搜索的思想，不断从新结点向下递归求解。

这样判负环会更简单些，只用一个辅助数组记录当前结点是否在递归栈中即可。

但是在拓扑关系较强时仍是广度优先搜索更优一些，所以考虑进行优化。

可以考虑在进行第一次 DFS 时，对扩展结点采取一些限制，以快速求得一个最优解，然后再进行第二次 DFS。

但这样仍然不如 BFS，BFS 的优势在于某个点在出队之前可能再次被更新，而得到了更优解进行下一次迭代，而 DFS 常常会用一个劣解进行深层的迭代。

那么可以迭代加深搜索，结合前面的限制方法，通过限制结点递归的深度并逐步放宽限制进行求解。

有两种比较好的限制方法：

1. 依次设置深度上限为 \(1,2,4,\dots,2^k\)；
2. 依次设置深度上限为 \(20,30,40,50,60,80,100,\dots\)

实验表明，在网格图中，限制深度的 DFS 效果大幅优于 BFS。

5. NTR 优化

维护一个叫作临时最短路树的东西，刚开始只有一个起点。

在 SPFA 的过程中，每次松弛边 \((u,v)\) 时将 \(v\) 的父亲设为 \(u\)。

\(v\) 可能存在后代，所以将其所有后代的 vis 标记清除；在 SPFA 过程中如果发现队首元素的 vis 为 \(0\) 就跳过。

因为如果我们能松弛边 \((u,v)\)，那么从边 \((u,v)\) 走一定比以前那种走法更优。

这里的描述参考自叫做 Raffica 的博主，他将这个研究结果发了论文并将论文发给了 Andrew.V.Goldberg 教授。Andrew.V.Goldberg 教授说这不是 Tarjan 算法吗？（以 Tarjan 命名的算法有几十种）

似乎出自 Tarjan 未完全公开发表的论文，感兴趣可以发 E-mail 和 Tarjan 要。

6. RMF 优化（Reconfiguration-Minimum-First）

设定一个阈值 \(k\)，并规定每个点的入队次数不能大于 \(k\)。

按这样跑完一遍 SPFA 之后，把所有点到起点的距离从小到大排序并依次加入队列（无法到达的不加），再跑一遍没有限制的 SPFA，会跑的飞快。

可以调整参数或者多跑几遍（类似模拟退火）。

7. UNVRS 优化

考虑 Swap-SLF 优化，如果队尾比队首小进行交换。那么我们可以考虑将队首后面若干个和队尾前面若干个也进行交换。

玄学优化

1. 边序随机

将读入的边随机打乱，之后再进行 SPFA。

2. 队列随机

每个结点入队时，以 \(\dfrac{1}{2}\) 的概率分别进入队首和队尾。

3. 队列随机优化

每若干次入队后，将队列元素随机打乱。

5. 猴排优化

每次取队首时，随机选一些数，然后取出其中最小的。

数据结构优化

通过更换使用的数据结构，一般是优先队列或者 ZKW 线段树。

在正边权上，使用这两种数据结构的 SPFA 与 Dijkstra 相当；负边权上可以会被卡成指数级别。

参考资料

1. OI-Wiki 最短路页面
2. spfa 的魔改方法
3. SPFA 算法的玄学方法
4. 知乎-如何看待 SPFA 已死这种说法
5. 迭代求解的利器——SPFA 算法的优化与应用-姜碧野
6. NTR 优化-Raffica
7. 复活 SPFA