Which maximum flow algorithm is this?

Правка en2, от akash_goel, 2015-07-21 22:33:19

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.

Теги max-flow, graph-theory, dinitz, edmond-karp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский akash_goel 2015-07-21 22:33:19 2 Tiny change: 'equired?\nQ2. Is t' -> 'equired?\n\nQ2. Is t'
en1 Английский akash_goel 2015-07-21 22:32:28 782 Initial revision (published)