1

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

Alexander R.
  • 133
  • 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". – A.E Jun 08 '14 at 23:35
  • @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...

     – Alexander R. Jun 09 '14 at 00:32
  • 1
    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. – G. Bach Jun 09 '14 at 00:42
  • I just realized the residual network is depicted on the left of you pictures. – G. Bach Jun 09 '14 at 01:08
  • 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 ??? – Alexander R. Jun 09 '14 at 10:20

1 Answers1

1

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

G. Bach
  • 267