形式陈述

最小费用流在有向网络上为每边给容量 $u_e$、单位费用 $c_e$，要求满足流守恒并发送指定流量（或满足供需），使 $\sum _e{c}_e{f}_e$ 最小。残量网络的正向边费用为 $c_e$，反向边费用为 $-c_e$。最优性可由残量网络不存在负费用环刻画。逐次最短增广路算法每次沿最小费用源汇路增广；存在负边时用势函数的约化费用保持非负并配合 Dijkstra。整数容量与供需下可得整数最优流。

直觉

最大流只关心能送多少，最小费用流还要决定从哪些路线送最划算。反向残量边允许撤销昂贵旧决策，负环则表示可在不改变供需的情况下继续降成本。

例子与边界

运输问题中供应点到需求点的边费用是单位运输成本。若未指定流量，零流可能平凡最优，因此必须说明目标流值或节点供需。负费用边本身不意味着无界；只有可无限循环且不受容量限制的负环才造成无界。直接每次选当前最便宜原图路径可能因已用容量和反向调整失败。势函数改变路径费用但保持同端点路径相对成本。

推论与应用

最小费用流统一运输、指派、带成本匹配、库存与排程，是网络流和线性规划之间的重要桥梁。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。