1
$\begingroup$

I'm learning flow networks. I learned Fulkerson algorithm, but there exists one point that is difficult for me.

Sorry for image, but I think this is best the way I can explain my problem. This is an example of Fulkerson algorithm execution from the book.

I can't reproduce the same result from step 2 ---> step 3 by running Fulkerson. How do I get flow (1/4)? I choose Cf = 8 (the minimum), then I need to sum previous flow with this new flow. Previous flow is 0 so 0 + 8 = 8...

I know that FLOW OUT = FLOW IN, and that FLOW(u,v) cant be less then CAPACITY(u,v), but how can I get to this results as in the book by running two last lines of the algorithm?

I am confused... need help. enter image description here

$\endgroup$
5
  • $\begingroup$ The reason is that you are not $actually$ sending 11 up that segment; you are making a decision to $not$ send down all the flow that you originally from $v_1$ to $v_2$ in the second step. Instead you are sending 1 up and getting the additional 7 from the top left corner node. The notation "$1/4$" just means "sending up 1 and capacity is 4". $\endgroup$
    – A.E
    Jun 8, 2014 at 23:35
  • $\begingroup$ @A.E I understand why it works, but, I cant't see how algorithm solve this "problem". Algorithm doesnt't "see" the graph, how it know that we need send 1 up and remove 7 from flow down? When I try to solve this example by running the algorithm step by step, I want to get something like: for u = v2 and v = v1 f(u,v) = f(u, v) + cf(p) // f(u,v) = 1 How get I right answer by running pseudo code? This lines are working fine for example on step 1 : Cf(p) = 4; for every (u,v) in p we do f(u,v) = f(u, v) + cf(p) and all flows setted as expected... But with step 3 I failed to do this... $\endgroup$ Jun 9, 2014 at 0:32
  • 1
    $\begingroup$ The algorithm uses the residual network, and in the residual network, there is an edge $(v_2, v_1)$ with capacity $11$ in the step that's confusing you. $\endgroup$
    – G. Bach
    Jun 9, 2014 at 0:42
  • $\begingroup$ I just realized the residual network is depicted on the left of you pictures. $\endgroup$
    – G. Bach
    Jun 9, 2014 at 1:08
  • $\begingroup$ I know. So, which data the algorithm uses, such that after executing line f(u,v) = f(u, v) + cf(p) => flow from v2 to v1 = 1 ??? $\endgroup$ Jun 9, 2014 at 10:20

1 Answer 1

1
$\begingroup$

The last two lines of the algorithm aren't exactly correct the way they are described; of course you can only send as much flow through an edge as its capacity allows, so lines 6 through 8 should be something like this:

\begin{align} x &:= min\{c(u,v) - f(u,v), c_f(u,v)\}\\ f(u,v) &:= f(u,v) + x\\ x &:= c_f(u,v) - x\\ f(v,u) &:= f(v,u) + x \end{align}

The first line makes sure that we only push as much flow through $(u,v)$ as its capacity and current flow allow; the third line ensures the same for $(v,u)$. If you like, you can put an $\textbf{if}\;(u,v) \in E$ and an $\textbf{if}\;(v,u) \in E$ around the assignments for $f(u,v)$ and $f(v,u)$, respectively.

Notice that the algorithm also doesn't explain how the residual network is constructed or adjusted, so that's implicitly assumed to be understood how you do that. It's a very short description of the central mechanism of the actual algorithm (which would take quite a few more lines to implement) with some minor details omitted/described only in prose ("while there exists a path in the residual network $G_f$" doesn't tell you how to find it, what the network is, or how to choose a path if several exist). This is quite common for more complex algorithms

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .