akash_goel's blog

By akash_goel, history, 9 years ago, In English

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:

  1. Find an augmenting path and maintain a parent array. Should be O(E) using BFS.
  2. Update the flow on all the edges on this path using the parent array. O(V) worst case. Update the max flow value.
  3. 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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your algorithm is Edmonds-Karp. Finding an augmenting path is indeed O(E), so the actual update of the flow O(V) can be ignored, as normally E>=V.

Having said that you can check in Wikipedia that the total complexity is O(V * E^2), so obviously the maximum number of steps is O(V*E). Explanation and link to a proof is given in Wikipedia, I doubt I can prove it myself.

The observations to prove the complexity are : After each iteration at least one edge is saturated, and each time an edge is saturated the distance from the edge to the source along the augmenting path is larger than it was the previous time it was saturated. If those two facts are proven the complexity is obviously O(V*E), as the longest distance is O(V) and there are E edges.

If you have any other questions, feel free to ask :)