最小费用流的逐次最短路法

残量费用 ​

最小费用流公理库最小费用流Minimum-cost flow在满足流量守恒与容量限制下最小化边费用总和的网络优化问题。 $f$ 的正向残量边容量为 $u_e-f_e$、费用 $c_e$；反向边容量为 $f_e$、费用 $-c_e$，允许撤销旧流。逐次最短路从一个可行流出发，每轮找残量网络最短 $s$–$t$ 路，按瓶颈容量增广，直到达到目标流量或无路。

势与 Dijkstra ​

负费用反向边使 Dijkstra 不能直接使用。维护顶点势 $\pi$，定义

$$c_{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v).$$

先以 Bellman–Ford 距离初始化，使所有可达残量边约化费用非负；此后用 Dijkstra 得距离 $d(v)$，对可达点更新 $\pi (v)\leftarrow \pi (v)+d(v)$。三角不等式保证新约化费用仍非负，而任意 $s$–$t$ 路的真实费用只与约化费用相差端点势常数。

最优性不变量 ​

势的对偶可行性等价于残量网络无负约化边；增广后新反向边的约化费用为零。达到目标流量时若残量网络无负费用环，就不存在保持流量而降低费用的循环调整，流为最优。

例子与边界 ​

先沿一条便宜路径送流后，后续更优组合可能需要走反向边撤销其中一段；反向费用取负正是表达这种修正。按单位容量增广会做 $F$ 轮，时间依赖数值总流量，是伪多项式；应按瓶颈增广或使用更强 cost-scaling 算法。势只更新可达点，存在负约化边时直接跑 Dijkstra 会给错误最短路。

复杂度与起始可行流 ​

若每轮用二叉堆 Dijkstra 为 $O(E\log V)$，增广轮数为 $A$，总时间 $O(AE\log V)$，另加一次 Bellman–Ford $O(VE)$ 初始化；$A$ 可等于总流量 $F$，因此不是强多项式。容量瓶颈增广会减少部分实例轮数，却不消除所有数值依赖。

有下界/需求时应先用可行环流归约找到起始流。若根本无可行流，SSP 不能从零流硬增广后宣称最优；原始可行性和费用最优性是两道证书。

一轮增广的数值核对 ​

假设当前势为 $\pi$，Dijkstra 得到约化距离 $d(v)$。对所有本轮可达点更新 ${\pi }^{\prime }(v)=\pi (v)+d(v)$；任意残量边的新约化费用满足

$$c_{{\pi }^{\prime }}(u,v)=c_{\pi }(u,v)+d(u)-d(v)\ge 0,$$

而最短路上的边等号成立。于是下一轮仍可使用 Dijkstra，且新增反向边的约化费用也为零。

一次路径增广量是路径剩余容量与尚缺流量的最小值。若容量整数且每轮至少增广 1，朴素复杂度可写 $O(FE\log V)$，其中 $F$ 是目标流量；这是假多项式界，不应只按输入位数称多项式。按瓶颈批量增广能减少某些实例轮数，但仍需报告采用的容量模型。

初始图有负费用边时，零势未必对偶可行；可先用 Bellman–Ford 求初始势，或从已知可行对偶开始。若存在可达负费用环且流量未固定，最优性与有界性问题也要先处理。

参考资料

• Ravindra Ahuja, Thomas Magnanti, James Orlin, Network Flows, 1993.
• Jack Edmonds, Richard Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, JACM, 1972.