Update Maximum Flow After Adding an Edge

Question

Consider we have a network flow and using Edmond-Karp algorithm, we already have the maximum flow on the network. Now, if we add an arbitrary edge (with certain capacity) to the network, what is the best way to update the maximum flow? I was thinking about updating the residual network regarding the new edge and again look for augmenting path until we find new max flow, but I am not sure if it works or if it is the best way!

Answer 1

After doing maxflow you know the amount of content each edge flowed.

So, when the cost of an edge changed you can do the following things :

1. Suppose, the content flowed by that edge is w.
2. Now do a forward dfs and a backward dfs from that edge and undone total w content from the edge it linked.

Here each edge is represented by x/y, where y means the edge capacity and x means the content it flowed.

Now you want to change the cost of edge 4->3 from 2 to 3.

All you have to do is do a forward and backward dfs from 4->3 edge and undone 2 weight from these edge as 4->3 flowed w=2 content.

Here is the process will look like :

Now you are almost done :)

3. Change the cost of the edge 4->3 from 2 to 3 and again try to find an augmenting path :)

Let me know if you find it difficult to understand or if i'm wrong somehow :)

Edit :

1. If new edge cost is greater than current cost than you won't have to undone the weight. You can just try to find an augmenting path changing the edge's capacity.

2. But if the capacity reduced, you have to undone the weight and try to find an augmenting path.

3. If a new edge added, you can just add the edge and try to find an augmenting path if available. that's it.