基于线性规划的图最大流问题的Goldberg-Tarjan算法求解示例

我将为您讲解Goldberg-Tarjan预流推进算法求解最大流问题的详细过程。

问题描述
给定一个有向图G=(V,E)，其中V是顶点集合，E是边集合。每条边(u,v)∈E有一个非负容量c(u,v)。指定源点s和汇点t。最大流问题的目标是从s到t输送尽可能多的流量，同时满足：

1. 容量约束：每条边上的流量不超过其容量
2. 流量守恒：除源点和汇点外，每个顶点的流入量等于流出量

算法思想
Goldberg-Tarjan算法采用预流推进策略，核心思想是：

• 允许顶点暂时"积水"（超额流量）
• 通过推进操作将超额流量推向邻接顶点
• 通过重标记操作调整顶点高度，确保流量能流向汇点

详细解题步骤

步骤1：初始化

1. 创建残余网络：对于原图中每条边(u,v)，在残余网络中创建两条边：

   • 前向边(u,v)容量为c(u,v)
   • 反向边(v,u)容量为0

2. 初始化高度函数：

   • h(s) = n（顶点总数）
   • 其他顶点h(v) = 0

3. 初始化预流：

   • 从源点s出发的所有边，流量等于容量：f(s,v) = c(s,v)
   • 其他边流量为0
   • 计算每个顶点的超额流量：e(v) = ∑f(u,v)

步骤2：推进操作（Push）
当存在超额流量顶点u（除s和t外）且e(u)>0时：

1. 在残余网络中寻找邻接顶点v，满足：

   • 残余容量r(u,v) = c(u,v) - f(u,v) > 0
   • h(u) = h(v) + 1（高度差为1）

2. 计算可推进的流量：
   Δ = min(e(u), r(u,v))

3. 执行推进：

   • 前向边：f(u,v) = f(u,v) + Δ
   • 反向边：f(v,u) = f(v,u) - Δ
   • 更新超额流量：e(u) = e(u) - Δ, e(v) = e(v) + Δ

步骤3：重标记操作（Relabel）
当顶点u有超额流量但无法推进时（所有邻接顶点高度≥u）：

1. 计算最小允许高度：
   h_min = min{h(v) | (u,v)在残余网络中有正容量} + 1

2. 重标记顶点高度：
   h(u) = h_min

步骤4：算法终止
当除源点s和汇点t外，没有顶点存在超额流量时，算法终止。此时进入汇点t的流量即为最大流。

实例演示
考虑简单网络：顶点{s,a,b,t}，边：

• s→a: 容量3
• s→b: 容量2
• a→b: 容量1
• a→t: 容量2
• b→t: 容量3

执行过程：

1. 初始化：h(s)=4，其他为0；从s推送流量到a和b
2. 顶点a有超额流量3，推送到b和t
3. 顶点b有超额流量，推送到t
4. 重复推进和重标记直到收敛

最终得到最大流为4，其中：

• s→a: 流量3
• s→b: 流量1
• a→b: 流量1
• a→t: 流量2
• b→t: 流量2

算法特点

• 时间复杂度：O(|V|²|E|)
• 实际效率通常优于传统增广路径算法
• 适合处理大规模稀疏网络