在O(|E|)迭代内终止的Ford-Fulkerson算法，而不考虑寻找增广路径的时间复杂度

Question

福特Fulkerson算法将在O(|E|f)时间内运行，其中f是最大流；但是，是否有方法使其运行O(|E|)？

让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充路径，使用与使用加权最短路径问题等查找路径相关的东西，但我能保证它在O(|E|)时间运行吗？

基本上忽略了寻找扩充路径所需的时间复杂度(即，无论算法是什么，让复杂度为O(1))。

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

Answer 1

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

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