Maximum flow with minimum flow on edges?

Question

I have a flow network with some edges and nodes. On the edges that leaves that source node, I would like to place some minimum flow, so that there's at least x flow on that edge (and if that's not possible I would like to know that). I've implemented the Ford-Fulkerson algorithm to find the maximum flow but I'm not sure how to adjust my algorithm to do this. I thought about decreasing the capacity on the edges that leaves the source node but that didn't work for me.

Could anyone please guide me in the right direction with this problem?

Thanks in advance!

Answer 1

You are looking for an algorithm for computing "flows with edge demands" or "flows with lower bounds." There are many straightforward algorithms for this. This set of notes details one possible approach, though if you were to do a few quick Google searches I bet you could find some more information on this.

Hope this helps!