Ford-Fulkerson肯定能够终止，因为流的单位为整数（Ford-Fulkerson，1962）。使用深度优先搜索的Ford-Fulkerson性能为O(E*mf)，取决于得到的最大流的值mf。简单地说，我们可以在每次迭代时向增广路中加入一个单位的流，但是容量巨大的网络可能会需要大量的迭代。在这种情况下，我们会非常惊讶地看到运行时间与问题的规模无关（例如顶点数或者边数），而是和边的容量相关。当使用广度优先搜索时（又名Edmonds-Karp算法），性能为O(V*E2)。广度优先搜索能够在O(V+E)的时间内找到最短的增广路，如果顶点比边数少很多，那么实际性能是O(E)。Cormen等（2001）曾证明基于广度优先搜索的Ford-Fulkerson算法是按照长度来依次求出增广路的，而不是像深度优先搜索那样花费大量的时间，尝试尽可能接近汇点。