如何看待 SPFA 算法已死这种说法？

123457015 · 发表于 2023-4-5 06:25

NOI2018 Day 1，T1 出题人卡了 SPFA 并在讲课时说其死了。

fwalker · 发表于 2023-4-5 06:30

好啊
这样如果有人觉得费用流用Johnson的方法消除负权，再跑Dijkstra不优美的话，就会去学网络单纯形了，然后就可以推广网络单纯形及其动态树优化了，然后就会有人深入了解动态树了，然后大家就都会用top tree代替树分治了。而这一切会加速OI算法工业化进程，促进OI严谨化、知识点体系化，把OI推向更高的平台。

量子计算9 · 发表于 2023-4-5 06:40

在决大部分费用流问题上SPFA还是好用的啊..
建图是特殊图，有些题还不知道 SPFA 能不能被卡..
如果你知道正确的 SPFA 判负环的姿势，在写消圈的时候会快上不少..
（当然消圈也能被替代就是了..
当然正权图用 SPFA 就是在作死.. 负权图感觉还是有点用的吧（反正代码长度和 Bellman-Ford 也差不多

量子计算9 · 发表于 2023-4-5 06:45

我极其反对使用 SPFA 来用一个假复杂度顶替 Bellman-Ford 的名字，因此我曾试图卡掉所有 SPFA 以及相关的优化，并且证明 SPFA 真的不行。
不过我遇到了一点小麻烦，还请有兴趣的诸位帮帮忙。(UPD：Hacked，出现过的大部分 SPFA 都死完了）

显然，普通 SPFA 是非常好卡的，只需要一个随机网格图（在网格图中走错一次路可能导致很高的额外开销），或者一个构造过的链套菊花（使得队列更新菊花的次数非常高）即可。很多奇怪写法的 SPFA 都只能通过两者中的至多一种，因此你只需要将图构造为网格套菊花即可。

对于我知道的其他比较著名或者比较有效的优化：

LLL 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾。
Hack：向 1 连接一条权值巨大的边，这样 LLL 就失效了。

SLF 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾。
Hack：使用链套菊花的方法，在链上用几个并列在一起的小边权边就能欺骗算法多次进入菊花。

SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。
Hack：如果边权之和很小的话似乎没有什么很好的办法，因为令边权之和为 $W$ ，那么令容错值为 $\sqrt W$ ，总复杂度似乎接近 $O((V+E)\sqrt W )$ 。我不确定这个复杂度对不对，但是 SPFA 确实在边权和小的时候跑得蛮不错的。所以卡法是卡 SLF 的做法，并开大边权，总和最好超过 $10 ^ {12}$ 。

mcfx 优化（thanks to @mcfx and @yfzcsc）：在第 $[L, R]$ 次访问一个结点时，将其放入队首，否则放入队尾。通常取 $L=2, R=\sqrt V$ 。
Hack：网格图表现优秀，但是菊花图表现很差。
P.S. 此优化与 SLF 带容错一起使用有更好的效果，可以使所需要的边权上升许多。

@raffica&#39;s NTR：详见如何卡spfa？ - raffica的回答 - 知乎。
Hack：菊花图表现很差。

SLF + swap：每当队列改变时，如果队首距离大于队尾，则交换首尾。
这个 SLF 看起来很弱，但却通过了所有 Hack 数据。而且，非常难卡。
还请各位认为 SPFA 必死的爷爷们，来亲手杀死这个苟延残喘的 SLF 吧。
UPD: Hacked by @negiizhao and @钟子谦。
Hack: 与卡 SLF 类似，外挂诱导节点即可。（是我菜了）

其实从原理上分析，所有 spfa 的优化都是为了使队列接近优先队列。然而，我们知道维护一个优先队列在目前来说是需要 log 的复杂度的，所以低于该复杂度的 一定能 Hack。

HuldaGnodim · 发表于 2023-4-5 06:50

属实。
在非负边权的图中，随手卡 SPFA 已是业界常识。在负边权的图中，不把 SPFA 卡到最慢就设定时限是非常不负责任的行为，而卡到最慢就意味着 SPFA 和传统 Bellman Ford 算法的时间效率类似，而后者的实现难度远低于前者。
SPFA 的受到怀疑和最终消亡，是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。

Update：
为了激励并推广卡 SPFA 这一行为，我提供一种最简单的卡 SPFA 的方法（同时适用于有向图和无向图）：
Step 1 生成一棵以起点为根的树，树高尽量高（比如 1 为起点时，可以令每个点 i 的父亲在 max(i-5,1) 到 i-1 随机），边权随机，作为最短路径树，同时直接递推求出每个点的带权深度 d(i)
Step 2 对于剩下的边，端点 (a, b) 随机，边权在 |d(b)-d(a)| 到 |d(b)-d(a)|+5 随机（如果是有向图则去掉绝对值符号，5 可以换成其他较小的正数）
这样生成的图中，次短路的条数非常的多，而 SPFA 一旦错误地进入了次短路的分支，就会使得一整棵子树被赋错误的距离，从而在后期不得不重新更新。而由于边权接近，剪枝的效果会受到很大影响。
这个生成方法代码简单易写，只需要大量的随机，不需要构造网格等特殊结构，生成器中甚至不需要建图，适合所有有责任心的出题人使用。

DungDaj · 发表于 2023-4-5 06:57

题目保证了没有负权边，为什么不用堆优化的 Dijkstra 呢？

		自动登录	找回密码
密码			立即注册