0
$\begingroup$

I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.)

enter image description here

If we first follow path S - A - C - T , we will get max flow equals to 1 as we cannot take path S - B - C - T (residual flow from C -- T became 0). I am also assuming that while doing BFS when we reach to t from c, we are stopping our BFS search and returning path. There is D left in the queue but we will ignore it as we have got one augmenting path. On next iteration we will move to B as S -- A edge residual capacity is 0.

If we first follow path as S - A - D - T and then S - B - C - T , we get max flow as 2.

I think, I am missing some basics, I belive algorithm does not dependend on which path I take first.

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Apr 27, 2016 at 9:32
  • $\begingroup$ What is the question here? $\endgroup$
    – Raphael
    Apr 27, 2016 at 9:32

1 Answer 1

3
$\begingroup$

I'm sure you have a misunderstanding. Try simulating the Edmonds-Karp algorithm by hand on the first example, then edit the question to show the residual graph you've got after it finishes. I'm sure you'll find there remains an augmenting path from $s$ to $t$ in the residual graph. If you don't draw the residual graph explicitly, you might fail to notice the path -- you can't do this in your head without drawing the graph on paper.

Many students get tripped up by the fact that there might be an augmenting path in the residual graph that looks like it goes "backwards" in the original graph; that's OK, and it still counts as an augmenting graph.

$\endgroup$
1
  • $\begingroup$ Thanks D.W. you are correct ! we cannot do it in our head. when we take first path S-A-C-T next time we get path S-B-C-A-D-T with backward edge from C--> A in residual graph. $\endgroup$
    – Bhushan
    Apr 27, 2016 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.