考虑有向图中的最小成本流问题，如下所示：$G=(V, E)$

(*) 最小值$\sum {c_{ij}f_{ij}}$

st: 对于每个$\sum_{j\in out(i)}{f_{ij}} - \sum_{j\in in(i)}{f_{ji}} =b(i)$$i\in V$

$f_{ij} \geq 0$

$in(i)$和分别是进入节点 i 和离开节点 i 的弧的集合。在公式中，上的流路由量，c_ ij) 上路由流的单位成本。对于每个节点 i，b(i) 是节点需求/供应。$out(i)$$f_{ij}$$(ij)$$c_{ij}$$(ij)$

声明：如果 * 是可行的并且对于所有弧，则最佳值为零。$c_{ij} \geq 0$$(i,j)\in E$