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

每轮保留已经作出的费用最优安排，再用当前最低边际费用增加一批流。反向弧允许重排旧路线，节点势则把这种可撤销的费用系统改写成 Dijkstra 可以处理的非负权图。

势不是另一个目标函数。对固定端点，路径约化费用与真实费用只差 $\pi (s)-\pi (t)$；排序没有改变。截断距离的作用是把本轮达到目标以后的区域统一抬高，保持整张残量图的价格约束。

图中四点都可达，距离为 $0,1,1,3$，均不超过 $d(t)=3$，所以截断更新恰好就是图上的 ${\pi }^{\prime }\leftarrow \pi +d$。

图中的一轮可以直接复算 ​

图上约化边费为 $s\to a:1,a\to b:0,b\to t:2,s\to b:4,a\to t:5$。最短路 $s-a-b-t$ 的约化费用为三，距离依次为零、一、一、三。更新势后，三条路径边的新约化费用都为零；两条旁路分别变为 $4+0-1=3$ 与 $5+1-3=3$。增广产生的三条反向记录也为零。若路径各有一单位余量且尚缺一单位，就增广一单位。

不可达点为什么也参与全局势 ​

取零势及残量弧 $s\to v$ 费用五、$x\to v$ 费用零，令目标为 $v$，而 $x$ 从 $s$ 不可达。若只把可达点的势加上距离，${\pi }^{\prime }(v)=5,{\pi }^{\prime }(x)=0$，则 $x\to v$ 的新约化费用为负五。截断更新同时令 ${\pi }^{\prime }(x)=5$，这条边仍为零。这个例子没有负环，错误发生在“全局非负”的不变量，而不是原问题突然不可行。

另一个错误是从任意可行流启动。取容量一、费用零的 $s\to t$，再加一个断开的单位容量环 $a\to b\to a$，费用为负二和零。若起始流已在 $s\to t$ 送满，目标 $F=1$ 立即满足，但费用零仍可通过填满该环降到负二。可行性归约只保证供需满足，没有自动完成费用优化。

容量与总成本 ​

设 $n$ 为顶点数、$m$ 为原弧数，成功增广 $A$ 次。带句柄二叉堆、邻接表及单位成本精确算术下，每轮最短路、势更新和路径更新为 $O((n+m)\log (n+1))$。计入一次可能失败的末尾搜索，总时间为

首项是显式虚拟源初始化的 Bellman–Ford；若已有可行势，可省去该项。工作空间为 $O(n+m)$。

若容量、起始流与 $F$ 都为整数，每次至少增加一单位，故 $A\le F-F_0$。按瓶颈批量增广能减少一些实例的轮数，却没有消除这种最坏数值依赖；二进制编码下该界是伪多项式。任意实容量时，每次操作的正确性仍成立，但不能再用“一次至少增加一”证明同一轮数界。

这一过程是原始—对偶方法理路原始—对偶方法Primal-dual method联合构造原始方案与对偶界，并通过可行性及计费关系证明最优或近似保证的算法框架。：流满足当前流值的原始约束，势证明其费用最优，零约化费用路径使两者同步推进。整数容量、非负初始费用的固定流量问题可以从零流、零势开始，这是常见而条件清楚的实现入口。

带下界和多点供需时，应先说明采用哪一种归约。找到任意可行环流之后，还需优化其残量环流，或采用从对偶可行伪流出发、逐步消除超额的另一种 SSP 形式。后者有不同的中间状态，不能把它与本页“每轮都是当前流值的最优可行流”混为一套初始化。

容量逐位缩放理路最小费用流的容量逐位缩放Capacity scaling for minimum-cost flow · Capacity bit scaling · Bit-scaling minimum-cost circulation从高位到低位读入整数容量，倍增旧流后只修复新单位余量造成的失衡，每位至多 m 次最短路增广。给出这种伪流修复的一个完整入口：倍增最优环流后，新出现的负约化费用方向每条只有一个单位余量；饱和它们产生至多m总正超额，再沿最短路补向亏缺点。它复用全图截断势更新，但阶段内不声称流已经满足原始守恒。

达到目标时可输出原弧流量与全局可行势，检查容量、守恒及每条正残量记录的约化费用。若求最小费用最大流，则持续增广到无路，最后另附残量可达割证明流值已最大。