最小费用最大流问题（Successive Shortest Path with Potentials 算法）
我将为您详细讲解最小费用最大流问题中的Successive Shortest Path with Potentials算法，这是一个结合了最短路径和势能函数的经典算法。
问题描述
最小费用最大流问题是在网络流问题的基础上，不仅要找到从源点s到汇点t的最大流量，还要在所有可能的最大流中，找到总费用最小的那个流。
输入：
- 有向图G=(V,E)
- 每条边e有容量c(e)≥0
- 每条边e有费用w(e)∈R
- 源点s和汇点t
目标：
在满足容量约束和流量守恒约束的前提下，找到从s到t的最大流f，使得总费用∑w(e)f(e)最小。
算法核心思想
Successive Shortest Path with Potentials算法基于以下关键观察：
- 残量网络中的负费用圈会降低总费用
- 通过势能函数重新赋权，可以将所有边权变为非负
- 在非负权图中，可以使用Dijkstra算法高效寻找最短路径
算法详细步骤
步骤1：初始化
- 初始流f(e)=0，对所有边e∈E
- 初始势能函数π(v)=0，对所有顶点v∈V
- 构建初始残量网络G_f
残量网络G_f的定义：
- 对于原图中的每条边(u,v)∈E，容量为c，费用为w
- 在残量网络中：
- 前向边：容量c-f，费用w
- 反向边：容量f，费用-w
步骤2：势能函数更新
势能函数π:V→R的作用是重新赋权，使得所有边权非负：
- 新的边权：w_π(u,v) = w(u,v) + π(u) - π(v)
关键性质：如果存在势能函数π使得w_π(u,v)≥0对所有边成立，那么残量网络中不存在负费用圈。
步骤3：主循环
当存在从s到t的增广路径时：
-
使用Dijkstra算法在重新赋权后的残量网络G_f中，找到从s到所有顶点的最短路径距离d(v)
-
更新势能函数：
π(v) = π(v) + d(v)，对所有v∈V这个更新保证了新的边权保持非负：
w_π'(u,v) = w(u,v) + π'(u) - π'(v)
= w(u,v) + [π(u)+d(u)] - [π(v)+d(v)]
= [w(u,v)+π(u)-π(v)] + [d(u)-d(v)]
≥ 0 + 0 = 0 -
沿最短路径增广：
- 找到从s到t的最短路径P（在重新赋权后的网络中）
- 计算路径P的瓶颈容量：bottleneck = min{残量容量(u,v) | (u,v)∈P}
- 沿路径P推送bottleneck单位的流量
- 更新残量网络
步骤4：终止条件
当无法找到从s到t的路径时，算法终止。此时得到的就是最小费用最大流。
算法正确性证明
势能函数的关键性质：
- 势能差π(u)-π(v)是w(u,v)的下界
- 重新赋权不改变最短路径结构
- 势能更新保持边权非负性
最优性条件（负圈最优性条件）：
一个流f是最小费用流，当且仅当其残量网络中不存在负费用圈。
通过势能函数，我们确保残量网络中不存在负费用圈，从而保证找到的流是最小费用流。
时间复杂度分析
- 每次迭代使用Dijkstra算法：O(|E| + |V|log|V|)
- 最多需要|f*|次迭代，其中f*是最大流值
- 总时间复杂度：O(|f*|·(|E| + |V|log|V|))
实例演示
考虑一个简单网络：
s → a → t
↘ ↗
b
边容量和费用：
- s→a: cap=2, cost=1
- s→b: cap=1, cost=3
- a→t: cap=2, cost=2
- b→t: cap=1, cost=1
- a→b: cap=1, cost=1
执行过程：
- 初始：f=0, π=0
- 第一次迭代：找到路径s→a→t，推送2单位流量
- 更新势能，继续寻找增广路径
- 最终得到最大流3，最小费用8
算法优势
- 高效处理负权边：通过势能函数消除负权影响
- 理论保证：确保找到最优解
- 实际性能好：相比普通的Successive Shortest Path算法，避免了多次Bellman-Ford调用
这个算法巧妙地将势能函数与最短路径算法结合，是解决最小费用最大流问题的高效方法。