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

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

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:如果边权之和很小的话似乎没有什么很好的办法,因为令边权之和为 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。

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 呢?
页: [1]
查看完整版本: 如何看待 SPFA 算法已死这种说法?