0
$\begingroup$

How do I use the Edmonds-Karp algorithm to calculate the maximum flow? I don't understand this algorithm $100\%$. What I need to know is about flow with minus arrow. Here is my graph:

the graph.

Our $1-6-11-12$, the flow is $4$. On the next iteration $1-2-4-11-6-7-9-12$, the flow on $6-11$ decrease on $3$, on other $+3$ on how do next? $1-3-5-11-6-8-10-12$? What will be with $11-6$? We must take $-3$, we will get negative flow on $6-11$ or what? Help me please.

2 Answers 2

1

You augment

  1. $1-6-11-12$ by $4$
  2. $1-2-4-11-6-7-9-12$ by $3$
  3. $1-3-5-11-6-8-10-12$ by $ 1$

and you are done: $12$ is no longer reachable from $1$ in the residual graph. You have already found the maximal flow.

  • 0
    how to describe this on 2-nd iteration, that we can go $f$rom 11 to 6 on road 1−2−4−11−6−7−9−12??2011-12-13
0

You are correct that the next step is to use the path $P$ given by 1-3-5-11-6-8-10-12, but since the flow from 6 to 11 is only 1, you can only send 1 unit of flow along $P$ (which is the solution rattle found). The flow in each edge must be non-negative at all times.

  • 0
    Yes, the maximum flow is 8. I don't understand your other questions. We don't "go" from 11 to 6; we reduce the flow in the arc 6-11 by redirecting 3 units of flow to the arc 6-7. If you have a textbook that does an example like this, then I guess you write it the same way your textbook writes it. If you don't have a textbook, then you search for "maximum flow" or "Edmonds-Karp" or something like that on the web until you find an example like this one, and then you write it the way it's written in the example.2011-12-13