Search code examples
algorithmgraph-theoryford-fulkerson

Ford Fulkerson algorithm increasing flow

Regarding the Ford Fulkerson algorithm with the path s-x-y-z-t we had to find out how the flow along that path could be increased.

The problem I'm having is, that I don't know how one gets the values in the solution.
Can someone explain?

enter image description here

Solution

  • In order to find an augmenting path in the Ford-Fulkerson algorithm, we need to look at the residual graph, which essentially allows us to

    • keep adding flow on nonsaturated edges or
    • remove existing flow from edges.

    It looks like your example consists of a subgraph, because the vertices X, Y and Z violate flow conservation (the sum of incoming flows should be zero at every vertex).

    In your example, we can

    • push 7 more along the SX edge;
    • push 4 more along the XY edge;
    • remove 3 units from the YZ edge;
    • push 4 more units along the ZT edge.

    Therefore, we can push at most 3 units from S to T without violating any capacity constraints. By doing that we end up with the flow network described in your second image.