前面一节介绍了Ford-Fulkerson算法。那么这个算法是否一定能够在有限步骤内结束？要多少步骤呢？

这个问题的答案是，该算法确实能够在有限步骤之内结束，但是至于需要多少步骤，就要仔细分析。

为了分析问题，需要假定图中所有边的容量都是整数。但是有个严重的问题，比如下图中，如果使用Ford-Fulkerson算法，需要迭代200次才能结束。

首先将所有边的容量都初始化为0。

第一次迭代和第二次迭代之后，两条边各增加了1。

到最后200次迭代之后整个算法才结束。

这还不算最坏的情况。因为整数最多可以取值大约21亿，那样可能就要迭代21亿次，算法的效率非常差。不过好在这种问题的解决办法还是比较简单的，因为每次选择路径的时候可以选择最宽的路径，这样迭代次数就少了很多。

从这个例子可以看出算法的效率跟路径的选择方式有关。下表总结了路径的不同选择方式对算法复杂度造成的影响。

• 最短路径，1/2 EV

• 最宽路径，E ln(EU)

• 随机路径，E U

• DFS路径，E U

其中U代表的是整数的最大取值范围。