最小費用流は線形計画問題

minimize

$ \sum_{(i,j)\in E} c_{ij} x_{ij}

subject to

$ 0 \le x_{ij} \le u_{ij}

$ \sum_i x_{ik} - \sum_j x_{kj} = b_k \quad (\forall k \in V)

where

c: cost

x: flow

u: capacity

b: 需要供給

スタートとゴールが1点であるような場合は正の頂点が1つ、負の頂点が1つある特殊形