为何Edmonds-Karp算法的时间复杂度低于Ford-Fulkerson算法？

Let’s break down the key differences in time complexity between these two max-flow algorithms, along with the reasoning behind their bounds:

• Ford-Fulkerson Algorithm: Its time complexity is O(FE), where F stands for the graph’s maximum flow value and E is the total number of edges. This bound comes from the fact that the number of augmenting paths we need to find depends directly on the flow value, which can be very large in worst-case scenarios.

• Edmonds-Karp Algorithm: A specialized implementation of Ford-Fulkerson that uses BFS to find the shortest possible augmenting path each iteration. Its time complexity is tighter at O(VE²), where V is the number of vertices in the graph.

Why Edmonds-Karp’s Complexity Lands at O(VE²)? #

The core logic hinges on how often an edge can act as a critical edge (an edge whose saturation allows us to increase the overall flow):

• Any single edge can be a critical edge at most O(V) times.
• Multiply this by the total number of edges E, and the total number of critical edge occurrences (which equals the total number of augmenting paths we’ll need to find) becomes O(VE).

This makes intuitive sense: every time an edge is used as a critical edge, the distance from the source vertex to its starting endpoint increases by at least 1. Since the maximum possible distance from the source to any vertex is O(V), each edge can only take on this critical role that many times before it can’t contribute to further flow increases.

Since each BFS to find an augmenting path runs in O(E) time, multiplying the total number of paths (O(VE)) by the time per path gives us the final time complexity of O(VE²).

内容的提问来源于stack exchange，提问作者oldselflearner1959