%%%
by acc_ @ 2019-11-15 14:23:11
%%%
by SaturdayForever @ 2019-11-15 14:27:36
建议重构代码,或跑分层图,或者两遍SPFA(误
by SaturdayForever @ 2019-11-15 14:29:20
@[SaturdayForever](/user/128461) 我用分层图A了,但是我想问一下spfa可以在有环的图上跑吗
by wrpwrp @ 2019-11-15 14:33:11
@[SaturdayForever](/user/128461) 求大佬指导
by wrpwrp @ 2019-11-15 14:33:32
可以
详见 [洛 谷 日 爆](https://www.luogu.org/blog/xhhkwy/spfa-hacker-orzorz)
by SaturdayForever @ 2019-11-15 15:00:45
SPFA在不被恶意卡的情况下,比dij还要快
都是在一般图上的最短路算法,当然可以在有环的图上跑。
#### 最短路总结
当范围小 或 用多源 或 最小环 时选择Floyd
如果不存在负环Dijkstra+堆优化稳定输出
否则SPFA快到飞起
普通的Dijkstra和Bellman-Ford因效率较低一般不采用
by SaturdayForever @ 2019-11-15 15:11:25
@[SaturdayForever](/user/128461)
陈年老帖了
谢谢大佬!!
by wrpwrp @ 2020-01-18 20:55:43