## Ford-Fulkerson algorithm

I’m studying ford-fulkerson algorithm from CLRS. there is something that I’m confused about.

``FORD-FULKERSON (G, s, t) 1 for each edge (u, v) ∈ E[G] 2 do f[u, v] ← 0 3 f[v, u] ← 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) ← min {cf(u, v) : (u, v) is in p} 6 for each edge (u, v) in p 7 do f[u, v] ← f[u, v] + c f ( p) 8 f[v, u] ← − f[u, v] ``

Most often in practice, the maximum-flow problem arises with integral capaci- ties. If the capacities are rational numbers, an appropriate scaling transformation can be used to make them all integral. Under this assumption, a straightforward implementation of FORD-FULKERSON runs in time O(E|f*|), where f* is the maximum flow found by the algorithm. The analysis is as follows. Lines 1–3 take time O(E). The while loop of lines 4–8 is executed at most |f*| times, since the flow value increases by at least one unit in each iteration. The time to find a path in a residual network is therefore O(V + E’) = O(E) if we use either depth-first search or breadth-first search. Each iteration of the while loop thus takes O(E) time, making the total running time of FORD-FULKERSON O(E|f*|).

So now my problem is that, to find a path we need o(E) and to iterate the for loop again we need o(E). so in total for every iteration in the while loop we need o(E^2). thus the running time of the algorithm would be O(|f*|E^2) not O(|f*|E). I’m really stuck, I don’t get it. please help me!

## Why does the Ford-Fulkerson Maximum flow algorithm not work for irrational capacities?

Can anyone help me understand why the Ford-Fulkerson algorithm does not work in the case of irrational capacities?

## Ford-Fulkerson pseudo-polynomial

Can somebody explain please why Ford-Fulkerson Algorithm has pseudo-polynomial complexity? I understand that the complexity in this case strongly depends on the capacities of the edges of the network, since we have $$O(|E|*f_{max})$$, but why is the algorithm still not polynomial?

## Ford-Fulkerson vs Edmonds-Karp

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…