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

每次最短残量路把新增流量送到当前最便宜的可修正路线；反向弧允许后来撤销早先选择。节点势把可能为负的原费用重写成非负约化费用，并在每轮最短距离更新后保持这一性质，所以后续仍可使用 Dijkstra。

例子与边界 ​

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

复杂度与起始可行流 ​

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

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

节点势维护约化费用非负，最短路增广同时更新原始流和对偶势，因此该算法是原始—对偶方法公理库原始—对偶方法Primal-dual method同时维护原问题与对偶问题的可行性和互补条件以构造解的算法框架。：可行流是原始对象，势与零约化费用边给出对偶互补条件。

一轮增广的数值核对 ​

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

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

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

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