View source for Min-cost flow problem

== Input ==

# A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.
# For each arc <math>a\in A</math>, there are two real numbers:
## The '''upper bound''' (ak.a. '''capacity) <math>u(a)\geq 0</math>.
## The (unit) '''cost''' or '''cost factor''' <math>c(a)\geq 0</math>.
# For each node <math>v\in V</math>, there is a real-valued '''balance''' <math>b(v)</math>.

'''Prerequisite for feasibility:''' <math>\sum_{v\in V}b(v)=0</math>.

== Output ==

A '''min-cost flow''' <math>f</math>, that is, a real number <math>f(a)</math> for each arc <math>a\in A</math> such that:
# ''Capacity constraints'': <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# ''Flow conservation condition'': For each node <math>v\in V</math>, it is <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)=b(v)</math>.
# ''Optimality'': The cost of <math>f</math>, <math>c(f):=\sum_{a\in A}c(a)\cdot f(a)</math>, is minimum among all flows that satisfy the capacity constraints and the flow conservation condition.

== Known Algorithms ==

# [[Negative cycle-canceling]]
# [[Successive shortest paths]]
# [[Successive shortest paths with reduced costs]]