最小费用最大流问题（Primal-Dual 算法）

我将为您详细讲解最小费用最大流问题中的Primal-Dual算法。这个算法结合了最大流和最短路径的思想，能够高效地找到流量最大且总费用最小的流方案。

问题描述

给定一个有向图G=(V,E)，其中每条边e=(u,v)有容量c(e)≥0和费用w(e)（可能为负）。源点s汇点t，目标是找到从s到t的最大流f，使得总费用∑(f(e)×w(e))最小。

算法核心思想

Primal-Dual算法基于以下关键观察：

1. 残量网络中，如果所有边的费用非负，那么沿着最短路径增广可以保证费用最小
2. 通过势函数（potential）可以将边的费用转换为非负，从而应用Dijkstra算法

算法步骤详解

步骤1：初始化

• 初始流f=0（所有边流量为0）
• 初始化势函数π(v)=0对所有v∈V
• 创建残量网络G_f，其中残量容量为c_f(u,v)=c(u,v)-f(u,v)+f(v,u)
• 残量边费用：原方向边w_f(u,v)=w(u,v)，反向边w_f(v,u)=-w(u,v)

步骤2：迭代增广过程
while (在残量网络中存在s到t的路径) do：

**步骤2.1：调整费用**
对每条边(u,v)∈E_f，计算调整后的费用：
w_π(u,v) = w_f(u,v) + π(u) - π(v)

这个调整的关键性质：对于任意路径P，调整后路径费用与原始路径费用只差一个常数π(s)-π(t)

**步骤2.2：寻找最短路径**
使用Dijkstra算法在调整后的残量网络中找到从s到t的最短路径P（按费用w_π）

**步骤2.3：检查负环**
如果发现从s到t的最短路径费用为负无穷，说明存在负费用环，算法需要特殊处理

**步骤2.4：沿路径增广**
计算路径P上的最小残量容量：Δ = min{c_f(u,v) | (u,v)∈P}
沿路径P推送Δ单位的流量：
- 对于前向边(u,v)：f(u,v) = f(u,v) + Δ
- 对于反向边(v,u)：f(v,u) = f(v,u) - Δ

**步骤2.5：更新势函数**
设d(v)为步骤2.2中计算出的从s到v的最短距离（按调整后费用）
更新势函数：π(v) = π(v) + d(v)

这个更新保证：在新的残量网络中，调整后的费用仍然保持非负

步骤3：输出结果
当无法再找到增广路径时，输出当前流f作为最小费用最大流

算法正确性证明要点

1. 势函数保持非负性：每次迭代后，对于所有边(u,v)∈E_f，有w_π(u,v)≥0
2. 最优性条件：当残量网络中不存在s到t路径时，当前流是最小费用最大流
3. 终止性：每次增广至少增加1单位流量，总流量有限，故算法必然终止

时间复杂度分析

• 每次迭代：O(|E| + |V|log|V|)（Dijkstra算法复杂度）
• 总迭代次数：最多为最大流值|f*|
• 总复杂度：O(|f*| × (|E| + |V|log|V|))

实例演示

考虑简单网络：s→a→t，s→b→t，a→b

• 边容量和费用：s→a(2,1), s→b(1,2), a→t(1,3), a→b(1,1), b→t(2,1)

执行过程：

1. 初始π=[0,0,0,0]，找到最短路径s→b→t，增广1单位流量
2. 更新势函数，找到新最短路径s→a→t，增广1单位流量
3. 继续寻找，最终得到最大流3，最小费用8

算法优势

• 处理负费用边能力强
• 实际效率通常优于理论最坏情况
• 结合了网络单纯形法和最短路径法的优点

这个算法是解决最小费用最大流问题的经典方法，在实际应用中表现出色。