基于线性规划的图最大流问题的连续最短路径增广算法（Successive Shortest Path Algorithm）求解示例

问题描述

给定一个有向图 \(G = (V, E)\)，其中每条边 \((u, v) \in E\) 有非负容量 \(c(u, v) \geq 0\)，以及单位流量费用 \(w(u, v)\)（可为正、负或零）。图中有一个源点 \(s\) 和一个汇点 \(t\)。最大流最小费用问题 要求找到一个从 \(s\) 到 \(t\) 的流，使得在不超过边容量的前提下流量最大，并且在所有最大流中总费用最小。

连续最短路径增广算法是一种用于求解 最小费用最大流 问题的经典算法。它基于一个核心思想：每次在残余网络中沿着从源点到汇点的最短路径（按费用计算）增广流量，直到无法继续增加流量为止。算法同时保证得到的流在每一步都是当前流量下的最小费用流。

解题过程

步骤1：理解算法基础概念

1. 残余网络（Residual Network）：

   • 对于当前流 \(f\)，定义残余容量 \(c_f(u, v) = c(u, v) - f(u, v) + f(v, u)\)。
   • 如果 \(c_f(u, v) > 0\)，则在残余网络中有一条从 \(u\) 到 \(v\) 的边，其容量为 \(c_f(u, v)\)，费用为 \(w(u, v)\)。
   • 如果原边有反向流量 \(f(v, u) > 0\)，则残余网络中会有一条从 \(v\) 到 \(u\) 的边，容量为 \(f(v, u)\)，费用为 \(-w(u, v)\)，表示可以退回流量以减少费用。

2. 最小费用流的条件：

   • 一个流 \(f\) 是当前流量下的最小费用流，当且仅当其残余网络中不存在负费用回路（这是关键的最优性条件）。

3. 算法框架：

   • 从零流开始。
   • 在残余网络中，寻找一条从 \(s\) 到 \(t\) 的最短路径（按费用求和）。
   • 沿该路径增尽可能多的流量（受路径上最小残余容量限制）。
   • 更新残余网络，重复直到无法从 \(s\) 到达 \(t\)（即达到最大流）。

步骤2：算法伪代码

1. 初始化：设流 \(f = 0\)，总费用 \(cost = 0\)。
2. 构建初始残余网络 \(G_f\)（与原图相同，因初始流为零）。
3. 当残余网络中从 \(s\) 到 \(t\) 存在路径时：
   • 使用最短路径算法（如 Bellman-Ford 或 Dijkstra 带势能修正）在 \(G_f\) 中找到从 \(s\) 到 \(t\) 的最小费用路径 \(P\)。
   • 计算路径 \(P\) 上的最小残余容量：\(\Delta = \min\{ c_f(u, v) \mid (u, v) \in P \}\)。
   • 沿 \(P\) 增广 \(\Delta\) 单位流量：
     • 对于 \(P\) 中每条正向边（与原图方向一致），增加流量 \(f(u, v) += \Delta\)。
     • 对于 \(P\) 中每条反向边（对应原图反向），减少流量 \(f(v, u) -= \Delta\)。
   • 更新残余网络 \(G_f\)（根据新的 \(f\) 调整边的容量和方向）。
   • 更新总费用：\(cost += \Delta \cdot \sum_{(u,v) \in P} w(u, v)\)。
4. 输出最终的最大流 \(f\) 和最小总费用 \(cost\)。

注意：如果原图存在负费用边，初始残余网络可能有负环，需要先用 Bellman-Ford 检测/消除，或使用势能初始化确保 Dijkstra 可用。

步骤3：举例说明

考虑以下有向图（边标注：容量, 费用）：

         (10, 4)
      a -------> b
     /|         / \
s-> / |        /   \ -> t
   /  |       /     \
  c   |      d       e
   \  |     /       /
 (5,1)\    /(8,2)  /(10,6)
    \  |  /     \ /
     v v v       v
      f -------> g
         (7, 3)

顶点：\(V = \{s, a, b, c, d, e, f, g, t\}\)
边：

1. \(s \to a\) : (10, 4)
2. \(s \to c\) : (5, 1)
3. \(a \to b\) : (10, 4)
4. \(a \to f\) : (∞, 2) # 假设很大容量
5. \(b \to d\) : (8, 2)
6. \(b \to e\) : (10, 6)
7. \(c \to f\) : (5, 1)
8. \(d \to g\) : (8, 2)
9. \(e \to t\) : (10, 6)
10. \(f \to g\) : (7, 3)
11. \(g \to t\) : (∞, 1) # 假设很大容量

过程迭代（简化演示关键步骤）：

1. 初始：\(f = 0\)，残余网络 = 原图。
2. 第一次最短路径：使用 Dijkstra（假设无边负费用）。最短费用路径：\(s \to c \to f \to g \to t\)，费用 = 1+1+3+1=6，最小容量 \(\Delta = \min(5,5,7,∞)=5\)。
   • 增广 5 单位流量。
   • 更新流：\(f(s,c)=5, f(c,f)=5, f(f,g)=5, f(g,t)=5\)。
   • 更新残余网络：相应边容量减少，添加反向边（容量5，费用负值）。
3. 第二次最短路径：残余网络中找最短 \(s \to t\) 路径。可能路径：\(s \to a \to f \to g \to t\)，费用=4+2+3+1=10，最小容量受限于 \(s \to a\) 的10和 \(f \to g\) 的剩余2（因第一次用了5），所以 \(\Delta = \min(10, ∞, 2, ∞) = 2\)。
   • 增广 2 单位流量。
   • 更新流和残余网络。
4. 继续：重复寻找最短路径并增广，直到 \(s\) 到 \(t\) 在残余网络中不连通（达到最大流）。
5. 终止：当无法找到 \(s \to t\) 路径时，当前流即为最大流，且总费用最小。

步骤4：算法正确性解释

• 最优性保证：每次增广后，残余网络中没有从 \(s\) 到 \(t\) 的路径时，流达到最大。由于每次增广都是沿当前残余网络中的最短路径，这保证了在每一步，对于当前流量，流是最小费用的（没有负费用回路）。
• 复杂度：取决于最短路径算法的选择。若用 Dijkstra（需势能避免负边），每次 \(O(m \log n)\)，最多增广 \(O(nU)\) 次（\(U\) 是最大边容量），故伪多项式时间。实际中常用容量缩放改进。

步骤5：与线性规划的联系

最小费用最大流可写为线性规划：

• 变量：\(f(u,v)\) 表示边 \((u,v)\) 上的流量。
• 目标：最小化 \(\sum_{(u,v)} w(u,v) f(u,v)\)。
• 约束：
  1. 容量：\(0 \leq f(u,v) \leq c(u,v)\)。
  2. 流量守恒：对每个非源汇点 \(v\)，\(\sum_u f(u,v) = \sum_u f(v,u)\)。
  3. 最大化流量：可添加虚拟边从 \(t\) 到 \(s\) 费用为 -∞，或分两阶段先求最大流再调费用。

连续最短路径算法本质上是求解该线性规划的一种原始-对偶方法，每次增广对应调整原始解，而最短路径计算隐含了对偶变量的更新（势能）。

总结

连续最短路径增广算法通过反复在残余网络中寻找并增广最短费用路径，逐步构建最小费用最大流。其正确性基于“无负费用回路”的最优性条件，效率可通过势能技巧和容量缩放提升。该算法直观展示了最小费用流问题的贪心增量求解思想，是网络流理论中的经典方法。