现在是没有可以高效处理负权/负环的图论算法了吗

ppip @ 2022-05-07 22:25:59

by ppip @ 2022-05-07 22:27:01

补充：单源最短路

by 山田リョウ @ 2022-05-07 22:28:56

@ppip 考虑到没有赋权也做不到吧

by 山田リョウ @ 2022-05-07 22:29:17

*负权

by ppip @ 2022-05-07 22:29:25

@cxy2022 dij 啊

by 山田リョウ @ 2022-05-07 22:29:54

就算是所有权值都为 1 跑 bfs，也要 O(n+m)，而 m 是可以到 O(n^2) 的

by Acc_Robin @ 2022-05-07 22:31:52

好像只有 O(n^2)（与 m 无关）的做法？

by ppip @ 2022-05-07 22:32:03

@cxy2022

假定 n（点数），m（边数） 同阶

by Liuyuzhuo @ 2022-05-07 22:35:07

有m log^8 m的，但你真的想学吗?

by _5011_ @ 2022-05-07 22:38:15

@ppip EI 发过一个 m\sqrt n\log w 的，而且据说有新的 m\log^8m\log w 的做法

by Liuyuzhuo @ 2022-05-07 22:39:27

错了，是m \log^8m\log v https://www.cnblogs.com/Elegia/p/16122335.html