Minimum-cost flow problem

In a flow network, you need to choose the cheapest path.

This is the directed graph.

G=(V,E)

(u,v)∈E

This is the edge.

c(u,v)>0 (c is the capacity)
f(u,v)≧0 (f is the flow)
a(u,v) is the cost of the path.

The cost of sending this flow is f(u,v)*a(u,v).

You choose the cheapest.

This is the total cost of the flow over all edges.

f(u,v)≦c(u,v)

Then, you think the maximum cardinality matching in G that has minimum cost.

G=(A∪B,E)

G'=(V'=A∪B,E'=E)

The capacity of all the new edges is 1 and their costs is 0.