I read Cormen and Wikipedia pages for Max flow algorithms, but I feel that I'm very confused right now.
In my understanding, a max flow would basically work as follows:
- Find an augmenting path and maintain a parent array. Should be O(E) using BFS.
- Update the flow on all the edges on this path using the parent array. O(V) worst case. Update the max flow value.
- Repeat the above steps until no more augmenting paths are found and return the max flow.
My questions are:
Ql. What is the limit on the number of times step 1 (bfs) is required? Q2. Is this Edmond Karp or Dinitz algorithm that I'm talking about?
This is my first post, so I hope you will point out any problems in the way I've framed this question. Thanks.