最小成本流问题的 Successive Shortest Path 算法 题目描述 我们有一个有向图 \( G = (V, E) \)，其中每条边 \( e = (u, v) \) 具有容量 \( c(e) \geq 0 \) 和单位流成本 \( w(e) \in \mathbb{R} \)。同时，每个顶点 \( v \) 有一个供需量 \( b(v) \in \mathbb{R} \)。如果 \( b(v) > 0 \)，表示 \( v \) 是 供应点 （供应量为 \( b(v) \)）；如果 \( b(v) < 0 \)，表示 \( v \) 是 需求点 （需求量为 \( -b(v) \)）；如果 \( b(v) = 0 \)，则是 中转点 。我们需要在所有顶点满足流量守恒（即对任意顶点 \( v \)，流出量减去流入量等于 \( b(v) \)）和边容量限制的前提下，找出一个可行流，使得总成本 \( \sum_ {e \in E} w(e) \cdot f(e) \) 最小化。这个问题被称为 最小成本流问题 （Minimum Cost Flow, MCF）。 题目要求：给定有向图、边容量、单位流成本、顶点供需量，求最小成本流。我们将讲解经典的 Successive Shortest Path (SSP) 算法 ，它适用于所有边成本非负的情况。 解题过程 SSP算法的核心思想是 增量地 沿着最短（最小单位成本）路径从供应点向需求点推送流量，类似于解决最大流问题时不断找增广路，但这里每次找的是 残量网络中成本最小的路径 。 1. 问题形式化与预备概念 设 \( f(e) \) 为边 \( e \) 上的流量，需满足： 容量限制：\( 0 \leq f(e) \leq c(e) \)。 流量守恒：对每个顶点 \( v \)，有 \[ \sum_ {(u,v)\in E} f(u,v) - \sum_ {(v,w)\in E} f(v,w) = b(v) \] 总供应等于总需求：\( \sum_ {v\in V} b(v) = 0 \)（否则无解）。 目标：最小化总成本 \( \sum_ {e\in E} w(e) f(e) \)。 残量网络 ：与最大流类似，对每条原始边 \( e = (u,v) \)，定义： 前向边：如果当前流量 \( f(e) < c(e) \)，则在残量网络中有一条边 \( (u,v) \)，剩余容量为 \( c(e) - f(e) \)， 单位成本为 \( w(e) \) 。 反向边：如果当前流量 \( f(e) > 0 \)，则在残量网络中有一条边 \( (v,u) \)，剩余容量为 \( f(e) \)， 单位成本为 \( -w(e) \) （因为沿反向边推流相当于减少正向流，成本要抵消）。 残量网络中的路径成本定义为路径上所有边单位成本之和。 势函数（Potentials） ：为了高效地重复寻找最短路径，我们引入势函数 \( \pi: V \to \mathbb{R} \)，用于 调整边的成本 ，使得所有调整后的成本非负，从而可以使用 Dijkstra 算法。调整后成本定义为： \[ w_ {\pi}(u,v) = w(u,v) + \pi(u) - \pi(v) \] 关键性质：在残量网络中， 任意路径的长度在原成本和调整后成本下相差一个常数 （路径起点和终点的势差），因此最短路径不变。 2. SSP 算法步骤详解 前提条件 ：所有边的原始单位成本 \( w(e) \) 非负（若允许负成本，需先用 Bellman-Ford 初始化势，这里假设初始非负，则初始势可全设为 0）。 算法步骤 ： 初始化 ： 流量 \( f(e) = 0 \) 对所有边 \( e \)。 势 \( \pi(v) = 0 \) 对所有顶点 \( v \)。 计算每个顶点的 当前不平衡量 \( \text{imbalance}(v) = b(v) \)（正值表示供过于求，负值表示需大于供）。 循环 ，直到所有顶点不平衡量为零： 在残量网络中，选择一个供应点（不平衡量 > 0）作为源点 \( s \)，选择一个需求点（不平衡量 < 0）作为汇点 \( t \)。 在残量网络中使用 Dijkstra 算法 ，基于 调整后成本 \( w_ {\pi} \) 计算从 \( s \) 到所有顶点的最短距离 \( d(v) \)（注意：因为 \( w_ {\pi} \) 非负，可用 Dijkstra）。 如果从 \( s \) 到 \( t \) 没有路径，则问题无解（或总供应无法送达某些需求）。 记下从 \( s \) 到 \( t \) 的最短路径 \( P \)（在原残量网络中，路径成本为 \( d(t) - \pi(s) + \pi(t) \)）。 沿着 \( P \) 推送尽可能多的流量，流量值 \( \Delta \) 取以下三者的最小值： 源点 \( s \) 的当前不平衡量（供应剩余）。 汇点 \( t \) 的当前不平衡量的绝对值（需求剩余）。 路径 \( P \) 上所有边的剩余容量。 更新流量：对路径 \( P \) 上的每条边，如果是前向边，增加流量 \( \Delta \)；如果是反向边，减少流量 \( \Delta \)。 更新顶点不平衡量： \( \text{imbalance}(s) \gets \text{imbalance}(s) - \Delta \)。 \( \text{imbalance}(t) \gets \text{imbalance}(t) + \Delta \)。 更新势函数，确保后续残量网络中调整后成本保持非负： 对每个顶点 \( v \)，设置 \( \pi(v) \gets \pi(v) + d(v) \)。（这一步是关键：新势能保证调整后成本仍非负，为下次 Dijkstra 做准备。） 当所有顶点不平衡量为零时，当前流即为最小成本流。 3. 算法正确性直观解释 每次迭代沿当前 最小单位成本路径 推流，类似于贪心：每次选择“最便宜”的方式送出一单位流量。 势函数的作用： 初始时 \( w_ {\pi} = w \geq 0 \)，可直接用 Dijkstra。 更新势 \( \pi(v) \gets \pi(v) + d(v) \) 后，对于残量网络中任意边 \( (u,v) \)，有 \[ w_ {\pi,\text{new}}(u,v) = w(u,v) + (\pi(u)+d(u)) - (\pi(v)+d(v)) = [ w_ {\pi}(u,v)] + [ d(u) - d(v) ] \] 由于 \( d(v) \leq d(u) + w_ {\pi}(u,v) \)（三角不等式），得 \( w_ {\pi,\text{new}}(u,v) \geq 0 \)，故下次 Dijkstra 仍适用。 算法终止时，所有供应送出，所有需求满足，且流是最小成本的（可通过线性规划对偶理论严格证明）。 4. 时间复杂度 每次迭代使用一次 Dijkstra（\( O(|E| + |V|\log|V|) \) 用二叉堆）。 最多迭代次数：每个供应点可能被选多次，但每次至少减少一个供应点的不平衡量，总迭代次数不超过总供应量 \( B = \sum_ {b(v)>0} b(v) \)。 因此，总复杂度为 \( O(B \cdot (|E| + |V|\log|V|)) \)。 注意：如果容量和供需量为整数，则 \( B \) 是整数。对于 最小成本最大流问题 （即所有供应点在超级源，所有需求点在超级汇），\( B \) 就是最大流值，此时 SSP 也称为 Primal-Dual 算法 。 5. 例子演示 考虑简单图：顶点 \( \{1,2,3\} \)，边与参数如下（容量，单位成本）： (1→2): 容量 3, 成本 1 (2→3): 容量 2, 成本 2 (1→3): 容量 2, 成本 4 供需：\( b(1)=3, b(2)=0, b(3)=-3 \)（即顶点1供应3，顶点3需求3）。 执行 SSP： 初始：流全为0，势全0，不平衡量：\( im(1)=3, im(3)=-3 \)。 迭代1：选 s=1, t=3。残量网络中所有边为前向边（容量满，成本原值）。Dijkstra 得最短路径 1→2→3，成本 1+2=3，调整后成本相同。推送流量 Δ = min(3,3, min(3,2)=2)=2。更新：流 f(1,2)=2, f(2,3)=2；im(1)=1, im(3)=-1；更新势：d(1)=0, d(2)=1, d(3)=3 ⇒ π(1)=0, π(2)=1, π(3)=3。 迭代2：s=1, t=3。残量网络： 边(1,2)：剩余容量 1，成本 1，调整后成本=1+0-1=0。 边(2,3)：已满，无前向边；有反向边(3,2)，容量2，成本-2，调整后成本=-2+3-1=0。 边(1,3)：容量2，成本4，调整后成本=4+0-3=1。 Dijkstra 从1出发：到2距离0（经(1,2)），到3距离1（经1→2→3，路径(1,2)+(3,2)反向？这里注意：从2到3在残量网络中只有反向边(3,2)，不能从2到3。所以从1到3的路径只能是1→3直接，成本1）。最短路径 1→3，成本1。推送流量 Δ = min(1,1,2)=1。更新：f(1,3)=1；im(1)=0, im(3)=0。结束。 最终流：f(1,2)=2, f(2,3)=2, f(1,3)=1，总成本 = 2×1 + 2×2 + 1×4 = 2+4+4=10。检查守恒：顶点1流出3，顶点3流入3，满足。 总结 SSP 算法是解决最小成本流问题的基础算法，其核心是 在非负成本残量网络中反复沿最短路径增广 ，并利用势函数维持成本非负以保证 Dijkstra 可用。该算法直观、易于实现，是学习网络流优化的重要范例。