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

2.1k Views Asked by At

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

There are 2 best solutions below

6
On BEST ANSWER

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.

4
On

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.