单位容量边缘的流动网络中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)，并且举一个例子不难如此复杂。