ppip @ 2023-05-24 10:28:59
使用bfs相比dfs有什么好处吗？感觉dfs也能跑？
by FerventTemp0 @ 2023-05-24 10:30:32
复杂度好像会退化
by Alex_Wei @ 2023-05-24 10:53:36
@ppip EK 算法的复杂度证明要求每次寻找的增广路长度最段
by ppip @ 2023-05-24 10:57:35
感谢。
by LCATreap @ 2023-05-24 11:21:02
使用 dfs 找无权图的最短路径经过特殊构造是可以被卡成指数级的。
bfs 不会。
而 EK 的时间复杂度的保证就是每次找的都是最短增广路。
by Disjoint_cat @ 2023-05-24 13:15:14
dfs 不就成 FF 了吗
by QAQ__ @ 2023-05-25 15:05:05
@Donotplaygame Ford Fulkerson 只是指那个框架，不包含找路径的部分吧（
至少 wp 上好像是这么说的？