algorithm - 无论寻找增广路径的时间复杂度如何，Ford-Fulkerson 算法都会在 O(|E|) 迭代内终止

Question

Ford Fulkerson 算法将在 O(|E|f) 时间内运行，其中 f 是最大流量；但是，有没有办法让它运行 O(|E|)？

使其运行小于 O(|E|f) 的解决方案之一是选择一条增广路径，该路径通过使用与通过加权最短路径问题等寻找路径相关的内容来最大程度地增加流量，但可以我保证它在 O(|E|) 时间运行？

基本上忽略找到增广路径所需的时间复杂度（即无论算法是什么，让复杂度为 O(1)）。

如果没有这种方法，反例是什么？如果是，我需要使用什么方法？

Answer 1

答案是肯定的。根据“流分解引理”，任何流最多分解为沿 E 条路径和循环的流。因此，原则上，您可以计算最大流量（根据您的假设，我们假设需要 O(1) 时间！），应用流量分解（证明是建设性的），并且只采用 <= E 增广路径。

上面的阻塞流参数不太适用，因为阻塞流是扩充路径的集合，而不是单个扩充路径。