SPFA 各种优化最坏情况下为什么会被卡成指数级
  • 板块灌水区
  • 楼主_thiscall
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/11/10 19:23
  • 上次更新2023/11/4 00:57:16
查看原帖
SPFA 各种优化最坏情况下为什么会被卡成指数级
414610
_thiscall楼主2021/11/10 19:23

感觉这个问题太低级,所以发到灌水区(勿喷)

网上说乱七八糟的 SPFA 优化可能被卡到指数级,但我很不理解:

以 SLF 优化为例,看起来这个优化只是改变了队列的顺序,并没有增加每个点的入队次数。那么如何把最坏情况卡到指数级?(最好有 n100,m1000n \leq 100, m \leq 1000 的 hack 数据)

2021/11/10 19:23
加载中...