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!