algorithm - 寻找网络中最大流量的福特富尔克森算法的运行时间分析

Question

我知道 ford fulkerson 的运行时间一般是 O(f*(n+m)) 其中 f* 是网络的最大流量，而 n ， m 是网络中的顶点和边的数量，但是什么如果所有边缘容量都以常数 C 为界，这将如何影响运行时间？

还是会影响运行时间？

Answer 1

假设一个简单的图，给定的约束基本上意味着不超过c*(n-1)离开源。这意味着f* <= c*(n-1)，并且由于c是恒定的，我们可以得出结论，没有修改的运行时间现在将是O(n^2+nm)。