algorithm - 具有单位容量边的流网络中 Ford-Fulkerson 方法的时间复杂度

Question

Ford-Fulkerson 算法是否会及时找到具有n顶点和m边的单位容量流网络（所有边都有单位容量）的最大流O(mn)？

Answer 1

O(M*f)是 Ford-Fulkerson 在整数容量图上的已知运行时间估计，其中M是边数和f最大流量的值，因为很容易在O(M)每个路径中找到增广路径，并且每条这样的路径都会增加流量至少 1。

如果你的图没有重复边（即没有一对边具有相同的开始和结束顶点），并且每条边都有单位容量，那么最大流量f不超过顶点数N（只是因为从源头开始只有N-1边），因此复杂性确实是O(N*M).

但是，如果你的图允许有重复的边（但每条边的容量仍然为 1），则f可以大于N，最多M，时间复杂度可以变为O(M*M)，不难举个例子这种复杂性发生了。