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.
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