SPFA她不香吗
by Lacrymabre @ 2019-09-27 07:11:25
SPFA不能活吗
by Provicy @ 2019-09-27 07:13:24
关于SPFA：他诈尸了
by ProtectEMmm @ 2019-09-27 07:29:18
你按照SPFA的思想，Dijkstra也来一个更新就入队，然后大概就可以处理负权，不过据说是非多项式级复杂度emmm
by ProtectEMmm @ 2019-09-27 07:30:59
SPFA是多项式级复杂度好吗
by ACAね @ 2019-09-27 07:36:35
有负权图难道出题人还会卡spfa吗？？
~~你别说，还真有~~之前好像在某一篇知乎中见过，但是可惜的是没保存下来；还有好像有一种叫tarjan（没错又是他）的最短路算法，时间复杂度稳定而可以处理带负权边的图，我也试着找了找，没找着.
（当然这是我很久以前看的了，所以记错也不是没有可能，权且看看就好）
总而言之csp的有负权的图用spfa处理绝对没问题.
by HRLYB @ 2019-09-27 07:38:24
好了。。此贴完结。我在费用流里找到了一堆dij跑负权的，但是，没有看懂这个神仙玩意儿。。不过话说一般费用流题数据也不会太大吧，spfa要卡也卡不动
by Ametsuji_akiya @ 2019-09-27 07:40:19
@[青行灯](/space/show?uid=19607) 我是说多次进队的dijkstra据说是非多项式级
by ProtectEMmm @ 2019-09-27 07:43:33
@[恶魔的笛子](/space/show?uid=33957)
不会是非多项式级吧？同一个节点进队$N+1$次就说明有负环了啊
by x义x @ 2019-09-27 08:14:00
@[x义x](/space/show?uid=58567) emmmm可能是我记错了，反正我就记得复杂度特别高
by ProtectEMmm @ 2019-09-27 08:15:02