Ford-Fulkerson算法的缺陷

分析Ford-Fulkerson时间复杂度

假设：每个边容量$c(e)$是$[1,C]$的整数

• Ford-Fulkerson结束时，最大流$val(f^{?})\le (n?1)C\le nC$。(最大值在只有一个宿点，其余全是源点且链路容量均为最大值$C$的情况下出现)
• 每次增广，流值大小至少增加1，因为链路瓶颈最小为1
• 用BFS或者DFS寻找一条增广路径的时间复杂度为O(n+m)，一般边数大于顶点数，取O(m)
• 因此最多$nC$步增广操作，就能达到最大流，总体时间复杂度为$O(mnC)$，由于容量$C$是按照位存储的，因此该算法仍是一个伪多项式算法。

Ford-Fulkerson算法不能快速收敛例子

最坏情况每次流值只增加1，最大流值为$2C$，因此最多需要$2C$次增广才能得到最大流

不能使用Ford-Fulkerson算法的情况

由于Ford-Fulkerson的前提假设为每个边容量$c(e)$是整数，因此边容量是整数是适用的。又有理数可以通过扩大倍数转化为整数，因此Ford-Fulkerson总体对有理数的适用的。下面证明存在不适用的无理数特例：

流网络构造如下：

其中$C$是一个足够大的容量，$r$为无理数，满足下列式子：

按照如下方式模式循环




模式观察：

最终会收敛到一个不是最大流的流

然而最大流值实际为$2C+1$