I am reading about maximum flows in Introduction to algorithms by Cormen etc.
Ford-Fulkerson algorithm is given below.
FORD-FULKERSON(G, s, t)
1 for each edge (u, v) in E[G] 2 do â[u, v] 0 3 â[v, u] 0 4 while there exists a path p from s to t in the residual network Gâ 5 do câ(p) min {câ(u, v) : (u, v) is in p} 6 for each edge (u, v) in p 7 do â[u, v] â[u, v]+câ(p) 8 â[v, u] - â[u, v]
While analyzing above algorithm author is mentioned as below.
The work done within the while loop can be made efficient if we efficiently manage the data structure used to implement the network G = (V, E). Let us assume that we keep a data structure corresponding to a directed graph G' = (V, E'), where E' = {(u, v) : (u, v) belong to E or (v, u) belongs to E}. Edges in the network G are also edges in G', and it is therefore a simple matter to maintain capacities and flows in this data structure. Given a flow â on G, the edges in the residual network Gâ consist of all edges (u, v) of G' such that c(u, v) - â[u, v] not equal to 0. The time to find a path in a residual network is therefore O(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 | â* |).
My questions on above text.
- Can any one please explain above paragraph easy to understand? I think both G and G' is same structually what differnce it makes?
- What does author mean by "dges in the network G are also edges in G', and it is therefore a simple matter to maintain capacities and flows in this data structure." ?
- How author came with The time to find a path in a residual network is therefore O(E') = O(E) if we use DFS or BFS?
Thanks for your time and help.