最小费用流

容量决定能通过多少，费用决定在相同供需下怎样安排更便宜。反向残量费用取负，正好退还撤销旧流的成本。负环是一条净供需为零的改进方向，即使它与指定的源汇路线不相连，也可能影响总费用。

势给每个顶点换一个价格基准。同端点路径的费用只增加同一个端点差，环费用则完全不变。因此非负约化费用既方便最短路计算，又给出没有降价循环的最优性证书。

两条各能发送一单位流的路径，单位费用分别为五和二。需求为一时取费用二的路线；需求为二时两条都须使用，总费用为七。若没有指定流值或供需，零流可能已最优，原问题就变了。

负环可以有界地改善一个已经达到目标流值的方案。设 $s\to t$ 容量一、费用零；另有与它断开的 $a\to b,b\to a$，容量均为一，费用分别为负二和零。只在 $s\to t$ 送一单位的费用为零；再把两条环弧都送满，需求不变而费用降到负二。有限容量使改进到此为止，最优值不是负无穷。只做源到汇搜索会漏掉这项改进。

费用自环也要单独计入：它不改变任何顶点的净需求，负费用时应在最优解中送满，正费用时可置零。最大流中“删掉自环不影响流值”的结论，因而不能直接用于费用目标。

若容量与需求均为整数，非空可行域存在整数最优流，费用本身可以是实数。其依据是有向点弧关联矩阵的全幺模性理路全幺模矩阵与整数顶点Totally unimodular matrix · Total unimodularity · TU用所有方形子式的 0、±1 性质控制逆矩阵分母，证明整数右端的线性约束产生整数顶点。及整数边界，而不是“每个可行流都是整数”。任意实容量下仍有上述最优性判据；依赖每轮至少增加一单位的离散终止证明则需要整数条件。

逐次最短路法理路最小费用流的逐次最短路法successive shortest path · SSP min-cost flow在残量网络反复沿最短费用路增广，并用顶点势保持约化费用非负。在每个当前流值已经费用最优的前提下，沿最短残量路增加流值，并保持可行势。零流是合适起点的一个常见情形，是原图没有负费用环；有负环时须另做初始化或采用能处理它的费用优化过程。

Network Simplex理路网络单纯形法network simplex method · network simplex algorithm把最小费用流的基表示为生成树，以约化费用选择基本环方向，再更新基或非基弧的边界状态。在网络流的生成树基之间换基；带下界与需求的环流归约理路带下界与需求的可行环流circulation with demands · flow with lower bounds把边流量下界和节点供需转成超级源汇最大流，并以饱和条件判定可行性。处理可行性。找到任意可行流之后，仍要通过负环判据或对偶证书核验费用最优，二者承担不同任务。

指派、运输、带成本匹配和库存调度都可用此模型。原始—对偶方法理路原始—对偶方法Primal-dual method联合构造原始方案与对偶界，并通过可行性及计费关系证明最优或近似保证的算法框架。把流与势同步维护，线性规划理路线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。则提供统一的目标与约束语言。实际复杂度应另报图大小、容量和费用编码、算术成本及采用的算法；问题定义本身没有一个固定的求解时间界。

最小平均环消去理路最小平均环消去Minimum mean cycle canceling · Minimum mean cycle cancelling · Goldberg–Tarjan cycle-canceling algorithm从任意可行流反复消去最小平均费用残量环，以紧误差收缩和固定弧证明强多项式轮数。从任意同需求可行流出发，按每条弧的平均费用选择改进环，以紧误差收缩和固定弧证明多项式轮数。容量逐位缩放理路最小费用流的容量逐位缩放Capacity scaling for minimum-cost flow · Capacity bit scaling · Bit-scaling minimum-cost circulation从高位到低位读入整数容量，倍增旧流后只修复新单位余量造成的失衡，每位至多 m 次最短路增广。逐位扩大整数容量并修复新单位造成的失衡；费用缩放理路最小费用流的费用缩放Cost scaling minimum-cost flow · Epsilon scaling · Goldberg–Tarjan cost scaling逐次减半约化费用误差，以饱和、推送和降势把伪流恢复为可行流，并给出容量数值无关的阶段操作界。则保持原容量，以逐步收紧的约化费用误差驱动局部放电。三者最后都交付本页的容量、供需及全残量可行势证书。