如何看待 SPFA 算法已死这种说法？
NOI2018 Day 1，T1 出题人卡了 SPFA 并在讲课时说其死了。 好啊这样如果有人觉得费用流用Johnson的方法消除负权，再跑Dijkstra不优美的话，就会去学网络单纯形了，然后就可以推广网络单纯形及其动态树优化了，然后就会有人深入了解动态树了，然后大家就都会用top tree代替树分治了。而这一切会加速OI算法工业化进程，促进OI严谨化、知识点体系化，把OI推向更高的平台。 在决大部分费用流问题上SPFA还是好用的啊..
建图是特殊图，有些题还不知道 SPFA 能不能被卡..
如果你知道正确的 SPFA 判负环的姿势，在写消圈的时候会快上不少..
（当然消圈也能被替代就是了..
当然正权图用 SPFA 就是在作死.. 负权图感觉还是有点用的吧（反正代码长度和 Bellman-Ford 也差不多 我极其反对使用 SPFA 来用一个假复杂度顶替 Bellman-Ford 的名字，因此我曾试图卡掉所有 SPFA 以及相关的优化，并且证明 SPFA 真的不行。
不过我遇到了一点小麻烦，还请有兴趣的诸位帮帮忙。(UPD：Hacked，出现过的大部分 SPFA 都死完了）
显然，普通 SPFA 是非常好卡的，只需要一个随机网格图（在网格图中走错一次路可能导致很高的额外开销），或者一个构造过的链套菊花（使得队列更新菊花的次数非常高）即可。很多奇怪写法的 SPFA 都只能通过两者中的至多一种，因此你只需要将图构造为网格套菊花即可。
对于我知道的其他比较著名或者比较有效的优化：
LLL 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾。
Hack：向 1 连接一条权值巨大的边，这样 LLL 就失效了。
SLF 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾。
Hack：使用链套菊花的方法，在链上用几个并列在一起的小边权边就能欺骗算法多次进入菊花。
SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。
Hack：如果边权之和很小的话似乎没有什么很好的办法，因为令边权之和为 https://www.zhihu.com/equation?tex=W ，那么令容错值为 https://www.zhihu.com/equation?tex=%5Csqrt+W ，总复杂度似乎接近 https://www.zhihu.com/equation?tex=O%28%28V%2BE%29%5Csqrt+W+%29。我不确定这个复杂度对不对，但是 SPFA 确实在边权和小的时候跑得蛮不错的。所以卡法是卡 SLF 的做法，并开大边权，总和最好超过 https://www.zhihu.com/equation?tex=10+%5E+%7B12%7D 。
mcfx 优化（thanks to @mcfx and @yfzcsc）：在第 https://www.zhihu.com/equation?tex=%5BL%2C+R%5D 次访问一个结点时，将其放入队首，否则放入队尾。通常取 https://www.zhihu.com/equation?tex=L%3D2%2C+R%3D%5Csqrt+V 。
Hack：网格图表现优秀，但是菊花图表现很差。
P.S. 此优化与 SLF 带容错一起使用有更好的效果，可以使所需要的边权上升许多。
@raffica's NTR：详见 如何卡spfa？ - raffica的回答 - 知乎 。
Hack：菊花图表现很差。
SLF + swap：每当队列改变时，如果队首距离大于队尾，则交换首尾。
这个 SLF 看起来很弱，但却通过了所有 Hack 数据。而且，非常难卡。
还请各位认为 SPFA 必死的爷爷们，来亲手杀死这个苟延残喘的 SLF 吧。
UPD: Hacked by @negiizhao and @钟子谦。
Hack: 与卡 SLF 类似，外挂诱导节点即可。（是我菜了）
其实从原理上分析，所有 spfa 的优化都是为了使队列接近优先队列。然而，我们知道维护一个优先队列在目前来说是需要 log 的复杂度的，所以低于该复杂度的 一定能 Hack。 属实。
在非负边权的图中，随手卡 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 一旦错误地进入了次短路的分支，就会使得一整棵子树被赋错误的距离，从而在后期不得不重新更新。而由于边权接近，剪枝的效果会受到很大影响。
这个生成方法代码简单易写，只需要大量的随机，不需要构造网格等特殊结构，生成器中甚至不需要建图 ，适合所有有责任心的出题人使用。 题目保证了没有负权边，为什么不用堆优化的 Dijkstra 呢？
页:
[1]