O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Minimum Cost Flow

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:

Supply satisfaction

For each source vertex siS, the sum of f(si,v) for all edges (si,v)∈E (the flow out of si) minus the sum of f(u, si) for all edges (u, si)∈E (the flow into si) must be less than or equal to sup(si). That is, the supply sup(si) at each source vertex is a firm upper bound on the net flow from that vertex.

Demand satisfaction

For each sink vertex tjT, the sum of f(u, tj) for all edges (u, tj)∈E (the flow into tj) minus the sum of f(tj,v) for all edges (tj,v)∈E (the flow out of tj) must be less than or equal to dem(tj). That is, the dem(tj) 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 s0) to be the source vertex for the flow network graph, and add edges (s0,si) for all siS whose capacity c(s0,si)=sup(si) and whose cost d(s0,si)=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 ( ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required