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

Question

福特-富尔克森算法会在O(mn)时间内找到具有n顶点和m边的单位容量流网络(所有边都有单位容量)的最大流吗？

Answer 1

O(M*f)是福特-富尔克森在整数容量图上的已知运行时间估计，其中M是边的数量，f是最大流的值，只是因为在O(M)中很容易找到每条增加的路径，并且每条这样的路径都至少增加了1。

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

然而，如果你的图允许有重复的边(但每条边的容量仍然是1)，那么f可以比N大，直到M，时间复杂度可以变成O(M*M)，并且不难举一个发生这种复杂性的例子。