Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
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
show 1 more comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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