1
$\begingroup$

In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results):

enter image description here

I have a problem understanding the part (c). The augmenting path is $s\rightarrow v_2\rightarrow v_1\rightarrow v_3\rightarrow t$ with a minimum weight of 8. This weight should be added or decreased in the right part of b:

$s\rightarrow v_2$: it was 0 by default, so now it has 8/13

$v_1\rightarrow v_3$: it has 4/12 adding 8 we would have 12/12

$v_3\rightarrow t$, it has 7/20; adding 8 holds 15/20

the problem is in the vertices: $v_1\rightarrow v_2$, for what I see it has only capacity 4 (b right part), so how to put the flow of 8 that it needs the procedure?. I see that at the end we finish up with a $v_1\rightarrow v_2$ with a value of 1/4, but I have my doubts how to get that result.

Is it that because $v_2:v_1$ has only capacity of 4, and I should put 8 of flow, that only 4 units pass through $v_2:v_1$ and the remaining 4 goes back from $v_1:v_2$? In that case it finds a value of 7/10; so it needs only 3 units giving us $v_1:v_2$ equals to 10, and because there is 1 unit remaining that goes from $v_2:v_1$ giving us 1/4?

Is that logic correct?

$\endgroup$
2
$\begingroup$

Prior to step (c) there are 7 units flowing from $v_1$ to $v_2$. The augmenting path pushes 8 units of flow from $v_2$ to $v_1$: 7 of these cancel the existing flow from $v_1$ to $v_2$, and 1 unit now flows from $v_2$ to $v_1$.

More generally, the residual network shows you how much flow you can push in each direction. The edge $v_2 \to v_1$ has a capacity of 11, so you can push up to 11 (=7+4) units in this direction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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