Implementation of Ford Fulkerson Algorithm with incremental updates

0
votes

I have implemented Ford Fulkerson algorithm and now trying to work on a variant of it.

Lets say the given graph with its solution is enter image description here

Supposing that after the solution is derived, capacity of one of the edges increases or decreases. We need to find an algorithm to get the new max Flow using the current solution and NOT from the start.

My suggestion is that, for this example, if we assume the capacity of 1-3 edge reduces from 12 to 8, then we need to do a BFS from 1 to start node and reduce the flow on each of the edges by 4 AND do a BFS from 3 to 5 and reduce the flow there also. But I am not sure if this is correct. Even if its correct, I am not getting an idea of how can I implement this?

Can anyone help me on this?

1
algorithmnetwork-flowford-fulkerson

1 Answers

0
votes

Yes, your approach is correct.

Use the same BFS you used to find the max Flow.

Keep in mind that:

  • you can't use the edge you're adjusting.
  • The edge might not be fully utilized so you may need to push back only a smaller amount of flow.