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.

Improve this question
$\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$ Commented Apr 27, 2016 at 9:32
  • $\begingroup$ What is the question here? $\endgroup$ Commented Apr 27, 2016 at 9:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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$ Commented Apr 27, 2016 at 5:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.