Min Cost Flow Algorithms (min cost flow)

bool MIN COST FLOW(

graph& G, edge array<int> lcap, edge array<int> ucap,
edge array<int> cost, node array<int> supply,

edge array<int>& flow)

MIN COST FLOW takes as arguments a directed graph G(V, E), an edge array lcap (ucap) giving for each edge a lower (upper) capacity bound, an edge array cost specifying for each edge an integer cost and a node array supply defining for each node v a supply or demand (if supply[v] < 0). If a feasible flow (fulfilling the capacity and mass balance conditions) exists it computes such a flow of minimal cost and returns true, otherwise false is returned. The algorithm is based on capacity scaling and successive shortest path computation (cf. [?] and [?]) and has running time O(| E | log U(| E | + | V | log | V |)).

bool MIN COST FLOW(

graph& G, edge array<int> cap, edge array<int> cost,

node array<int> supply, edge array<int>& flow) This variant of MIN COST FLOW assumes that lcap[e] = 0 for every edge e ∈ E.

int MIN COST MAX FLOW(

graph& G, node s, node t, edge array<int> cap,

edge array<int> cost, edge array<int>& flow) MIN COST MAX FLOW takes as arguments a directed graph G(V, E), a source node s, a sink node t, an edge array cap giving for each edge in G a capacity, and an edge array cost specifying for each edge an integer cost. It computes for every edge e in G a flow flow[e] such that the total flow from s to t is maximal, the total cost of the flow is minimal, and 0 ≤ flow[e] ≤ cap[e] for all edges e. MIN COST MAX FLOW returns the total flow from s to t.