最小成本流问题的 Successive Shortest Path 算法

题目描述
假设我们有一个有向图 G=(V, E)，其中每条边 e∈E 上有两个属性：容量 c(e) ≥ 0 和单位流量成本 w(e)（可以为负）。同时，对每个顶点 v∈V 定义其供给/需求 b(v)：若 b(v) > 0，则表示顶点 v 是一个供给点（source），可以提供 b(v) 的流量；若 b(v) < 0，则表示顶点 v 是一个需求点（sink），需要接收 |b(v)| 的流量；若 b(v) = 0，则为转运点。目标是找到一个可行流 f: E → R+，满足：

1. 容量限制：对于每条边 e，0 ≤ f(e) ≤ c(e)。
2. 流量平衡：对于每个顶点 v，∑{(u,v)∈E} f(u,v) - ∑{(v,u)∈E} f(v,u) = b(v)。（即流出减流入等于净供给）
3. 总成本 ∑_{e∈E} w(e)·f(e) 最小。

这个问题称为“最小成本流问题”（Minimum Cost Flow, MCF）。本题目要求解释求解此问题的“Successive Shortest Path（SSP）”算法。

解题过程

SSP 算法的核心思想是迭代地沿着最短（关于某种成本度量）路径从供给点向需求点发送流量，直到所有顶点的供给/需求被满足。这可以看作是在残余网络中反复寻找最小成本增广路径的过程。

1. 基本概念与转换

• 为保证存在可行解，通常假设 ∑_{v∈V} b(v) = 0（总供给等于总需求）。
• 为了方便，可引入一个虚拟的超源 S 和超汇 T，但 SSP 一般直接处理顶点供给需求。
• 算法维护一个可行流 f（初始时通常设 f(e)=0，前提是该流满足容量限制与平衡条件；若存在负成本边，初始零流可能不满足成本最优性，需用势能保证非负残余成本，见后文）。
• 对每条边 e = (u,v)，定义其残余容量：
  • 正向边：r(e) = c(e) - f(e)，保留原成本 w(e)。
  • 反向边：r_rev = f(e)，成本为 -w(e)（表示退回流量可节省成本）。
• 残余网络 G_f 包含所有 r > 0 的边。

2. 算法框架（朴素 SSP）

初始化：f(e) = 0 对所有 e ∈ E
while 存在供给点（b(v) > 0） do
    在残余网络 G_f 中，以边成本 w 为距离，计算从任意供给点 s（b(s) > 0）到任意需求点 t（b(t) < 0）的最短路径 P（路径成本最小）。
    沿路径 P 推送流量 Δ = min{ b(s), -b(t), min_{e∈P} r(e) }。
    更新：
        f(e) += Δ 对 P 中正向边，f(e) -= Δ 对反向边。
        b(s) -= Δ, b(t) += Δ。

但该朴素版本存在问题：若图中有负成本边，残余网络可能出现负权环，无法直接用 Dijkstra 求最短路径。为此，需引入势能（Potentials） 保证所有残余边成本非负。

3. 引入势能以处理负边

• 为每个顶点 v 维护势能 p(v)，初始 p(v)=0。
• 定义缩减成本（reduced cost） w_p(u,v) = w(u,v) + p(u) - p(v)。
• 关键性质：对于任何路径 P，其原始成本与缩减成本满足 ∑_{(u,v)∈P} w(u,v) = ∑ w_p(u,v) + p(v_start) - p(v_end)。因此路径在原始成本下的最短性等价于在缩减成本下的最短性。
• 如果我们能保持所有残余边的缩减成本非负，就可在 G_f 中用 Dijkstra 算法求最短路径。

4. 完整的 Successive Shortest Path with Potentials 算法
步骤：

输入：有向图 G=(V,E)，容量 c(e)≥0，成本 w(e)，供给/需求 b(v) 满足 ∑ b(v)=0。
输出：最小成本可行流 f。

初始化：
    f(e) = 0 对所有 e ∈ E
    p(v) = 0 对所有 v ∈ V
    B_supply = {v | b(v) > 0}  // 供给点集合
    B_demand = {v | b(v) < 0}  // 需求点集合

while B_supply 非空 do
    1. 构造残余网络 G_f：
        对每条边 e=(u,v)：
            若 f(e) < c(e)，加正向边 (u,v)，残余容量 r = c(e)-f(e)，成本 w_p = w(u,v)+p(u)-p(v)
            若 f(e) > 0，加反向边 (v,u)，残余容量 r = f(e)，成本 w_p = -w(u,v)+p(v)-p(u)
    2. 在 G_f 中，选取任意供给点 s ∈ B_supply，以缩减成本 w_p 为距离，运行 Dijkstra 算法求出从 s 到所有顶点的最短距离 d(v)（若 v 不可达，d(v)=∞）。
    3. 从 s 出发，选择一个可达的需求点 t ∈ B_demand 使得 d(t) 最小。若没有可达需求点（d(t) 均为 ∞），则问题不可行（但供给/需求和为零时一般可行）。
    4. 沿最短路径 P（在 G_f 中从 s 到 t 的路径）推送流量 Δ = min{ b(s), -b(t), min_{e∈P} r(e) }。
    5. 更新流 f 和供给/需求：
        对 P 中每条边（按方向）：
            若为正向边，f(e) += Δ
            若为反向边（对应于原图中的反向），f(e) -= Δ
        b(s) -= Δ, b(t) += Δ
        若 b(s) 变为 0，将其从 B_supply 移除
        若 b(t) 变为 0，将其从 B_demand 移除
    6. 更新势能：对所有 v ∈ V，p(v) = p(v) + d(v)  （如果 d(v)=∞，则保持 p(v) 不变）
        注意：此处 d(v) 是步骤 2 中从 s 出发以缩减成本计算的最短距离。更新后，G_f 中所有边（包括新增的残余边）的缩减成本仍保持非负（这是 Dijkstra 最短距离的性质所保证的）。
结束

5. 算法正确性要点

• 势能 p 的更新保持性质：更新后，对于 G_f 中的任何边 (u,v)，其新的缩减成本 w_p'(u,v) = w(u,v) + (p(u)+d(u)) - (p(v)+d(v)) = [w(u,v)+p(u)-p(v)] + d(u) - d(v) = 旧缩减成本 + d(u) - d(v)。
• 由 Dijkstra 的最短距离性质，d(v) ≤ d(u) + w_p(u,v)，因此 d(u) - d(v) + w_p(u,v) ≥ 0，即 w_p'(u,v) ≥ 0。因此所有残余边缩减成本保持非负，下一轮可继续用 Dijkstra。
• 算法每次迭代将至少一个供给点或需求点的供给/需求清零，故最多 O(|V|·U) 次迭代（U 为总供给量），实践中常视为 O(|V|) 次。
• 最终得到的是最小成本流，因为每次沿缩减成本最短路径增广保持了最优性条件（互补松弛条件）。

6. 时间复杂度

• 每次迭代：一次 Dijkstra（O(|E| + |V| log |V|) 使用优先队列）。
• 迭代次数：最多 |V| 次（因为每次迭代至少清零一个顶点）。
• 总复杂度：O(|V|·|E| log |V|) 或 O(|V|^2 log |V| + |V|·|E|) 取决于实现。

7. 举例说明
考虑简单网络：V={1,2,3}，b(1)=2（供给），b(2)=-1，b(3)=-1（需求），边：
(1,2): c=5, w=1
(1,3): c=5, w=3
(2,3): c=5, w=1
初始 f=0, p=0。

• 迭代1：从供给点1出发，最短路径到需求点2（成本1），推送 Δ=min(2,1,5)=1。更新 f(1,2)=1, b(1)=1, b(2)=0。更新势能 p(1)=0, p(2)=1, p(3)=∞（暂未达，保持0）。此时 G_f 中有残余边：(1,2) 容量4 成本1；(1,3) 容量5 成本3；(2,1) 容量1 成本-1（缩减成本？需重新计算）。
• 为保持缩减成本非负，需用势能重新计算。实际上算法会在每次迭代后更新 p，之后所有边缩减成本非负，下一轮 Dijkstra 可正常进行。
• 迭代2：从1出发，最短路径到需求点3（路径1→2→3 成本1+1=2，或1→3成本3），推送流量 Δ=min(1,1,4)=1 沿路径1→2→3。更新流，b(1)=0, b(3)=0，结束。

总成本 = 11 + 11 + 1*1 = 3，是最小成本。

8. 注意事项

• 如果图中存在负成本圈，该算法依然有效，因为势能机制避免了负权最短路径计算。
• 初始零流是可行的，但如果存在负成本圈且容量为正，零流可能不是最优，算法能通过增广消除负圈的影响。
• 该算法是“Primal-Dual”思想的一个实例，每次迭代解决一个最短路径子问题，逐步趋近最优。