最小费用流

最大流只关心“能送多少”，最小费用流还要在满足给定流量或供需的前提下决定“走哪条路线最划算”：容量决定流量上限，费用决定边际选择。残量网络中的反向边费用取负，使算法可以撤销先前昂贵选择；负环则表示能在不改变供需的情况下降低成本。最短增广路法每次寻找从源到汇的最低边际费用路径，但负费用边要求 Bellman–Ford 或势函数约化。

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

两条可发送一单位流的路径费用分别为 $5$ 与 $2$，需求为一单位时应走费用 $2$ 路径；需求变为两单位且容量各一，则总费用为 $7$。若先走一条局部便宜路径阻塞后续组合，残量反向边允许重排流。

存在可达负费用环时，若环还有残量容量，可沿环降低总费用而不改变净流量；算法必须检测或通过最优性条件排除。势函数要求约化成本非负且按正确方向更新，原图有负边时不能直接用普通 Dijkstra。

最小费用流结合 最大流公理库最大流Maximum flow在容量与流守恒约束下最大化源到汇净流量的问题。 的可行性、最短路公理库最短路问题Shortest-path problem在有限有向实权图中寻找源点到各顶点的最小有向游走成本。 的边际选择与 线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。 的对偶结构，是网络流和线性规划之间的重要桥梁。指派、运输、带成本匹配、库存和资源调度都可建模为最小费用流；原始—对偶方法公理库原始—对偶方法Primal-dual method同时维护原问题与对偶问题的可行性和互补条件以构造解的算法框架。 解释节点势与互补松弛。

问题页应把求解路线分开：连续最短路公理库最小费用流的逐次最短路法successive shortest path · SSP min-cost flow在残量网络反复沿最短费用路增广，并用顶点势保持约化费用非负。每次在残量网络增广并用势保持非负约化成本；Network Simplex公理库网络单纯形法network simplex method · network simplex algorithm把最小费用流的基表示为生成树，以约化费用选入基弧并沿基本环完成枢轴。在生成树基之间 pivot，工程行为与最坏理论不同；带下界需求环流公理库带下界与需求的可行环流circulation with demands · flow with lower bounds把边流量下界和节点供需转成超级源汇最大流，并以饱和条件判定可行性。先处理可行性和基准流。负成本边、负环与容量整数性决定算法条件，不能把某一实现复杂度写成问题固有成本。