# How to calculate the maximum flow in this graph by the Edmonds-Karp algorithm?

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:

.

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.

-

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.

-
8 is result yes? – DPS Dec 12 '11 at 18:36
math.stackexchange.com/users/11653/rattle flow can't be negative? – DPS Dec 12 '11 at 19:03
I am not sure I understand your question. Do you know what a residual graph is? – Jesko Hüttenhain Dec 12 '11 at 22:31
Oh and yea, the value of the maximum flow is 8. – Jesko Hüttenhain Dec 13 '11 at 13:12
how to describe this on textbook) ? a know how it works, but how to write this ))) – DPS Dec 13 '11 at 16:51

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.

-
8 is result yes? – DPS Dec 13 '11 at 12:44
how to describe this on textbook) ? a know how it works, but how to write this ))) – DPS Dec 13 '11 at 16:52
how to describe this on 2-nd iteration, that we can go from 11 to 6 on road 1−2−4−11−6−7−9−12?? – DPS Dec 13 '11 at 18:57
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. – Gerry Myerson Dec 13 '11 at 22:42