Ford-Fulkerson vs Edmonds-Karp

Question

I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead of DFS) variant of Ford-Fulkerson algorithm.

The point is on time complexity, Ford-Fulkerson algorithm has $O(|E||f_{max}|)$ whereas Edmonds-Karp is presented to run in $O(|V||E|^2)$. My main is question is then, how can I decide which of these algorithm is the faster on an arbitrary max-flow problem ?

I feel very unconfortable with the $f_{max}$ even if I understand it, because determining it is the goal of the algorithm so estimating it is likely to be hard on the very general case. Depending on problem, $f_{max}$ may be very high with respect to $|E|$, even if one can possibly apply a scale factor on all edges.

I also do not understand where the runtime difference comes from. Generally BFS and DFS have the same expected runtime, the difference between them is more on problem dependant space requirement and features like shortest path, topological order...

Answer 1

Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former. In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other variant of FF in preference to EK).

The above does not imply that EK is faster than a particular (say, DFS-based) variant of FF on any particular instance.

BFS and DFS have the same runtime, but DFS only promises to find a path from source to sink in the residual graph -- not necessarily a shortest possible such path, which BFS does promise. It's possible to show that no modification to the residual graph ever reduces the distance from the source to any vertex; with this, and the fact that BFS always finds a shortest path, it's possible to show that after finding at most $|V||E|$ augmenting paths, no source-to-sink path remains in the residual graph. This page gives a full proof -- I've only skimmed it, but note that when it says that "That is, [the distance from the source to all other nodes] is always increasing", it in fact means (or should mean) that this never decreases -- that is, the distance from the source to a particular node can stay the same after an augmentation, or it can be larger, but it can never be smaller.