javashortest-pathbreadth-first-searchford-fulkersonedmonds-karp

Ford-Fulkerson implementation java


I'm trying to learn to implement the Ford-Fulkersons algorithm in java and found some help on the internet but I got stuck at this snippet of code

        // update residual capacities of the edges and
        // reverse edges along the path
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }

I sort of understand how it works thanks to the comment, but not completely sure why it's required. Why do you need to subtract?

Source: http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/


Solution

  • If you can push a flow in either direction along an edge, then the net flow from A to B has to be equal in magnitude and opposite in sign to the net flow from B to A.

    It's just like in circuit analysis: if 5 amps of current flow from A to B, then -5A of current flow from B to A.

    A     Resistor      B
    O-----[======]------O
      5A ->
    
    A     Resistor      B
    O-----[======]------O
                 <- -5A
    

    Hence, by pushing "more" from A to B, you have to reduce the amount being pushing from B to A by a corresponding amount.