To solve a Minimum Cost Flow problem we need only construct a flow network graph and ensure that it satisfies the criteria discussed earlier—capacity constraint, flow conservation, and skew symmetry—as well as two additional criteria:
For each source vertex s_{i}∈S, the sum of f(s_{i},v) for all edges (s_{i},v)∈E (the flow out of s_{i}) minus the sum of f(u, s_{i}) for all edges (u, s_{i})∈E (the flow into s_{i}) must be less than or equal to sup(s_{i}). That is, the supply sup(s_{i}) at each source vertex is a firm upper bound on the net flow from that vertex.
For each sink vertex t_{j}∈T, the sum of f(u, t_{j}) for all edges (u, t_{j})∈E (the flow into t_{j}) minus the sum of f(t_{j},v) for all edges (t_{j},v)∈E (the flow out of t_{j}) must be less than or equal to dem(t_{j}). That is, the dem(t_{j}) at each target vertex is a firm upper bound on the net flow into that vertex.
To simplify the algorithmic solution, we further constrain the flow network graph to have a single source vertex and sink vertex. This can be easily accomplished by taking an existing flow network graph with any number of source and sink vertices and adding two new vertices. First, add a new vertex (which we refer to as s_{0}) to be the source vertex for the flow network graph, and add edges (s_{0},s_{i}) for all s_{i}∈S whose capacity c(s_{0},s_{i})=sup(s_{i}) and whose cost d(s_{0},s_{i})=0. Second, add a new vertex (which we often refer to as tgt, for target) to be the sink vertex for the flow network graph, and add edges ( ...
No credit card required