基于线性规划的图最大流问题的容量缩放算法求解示例
我将为您讲解使用容量缩放算法求解图最大流问题的完整过程。这个算法结合了Ford-Fulkerson方法的基本思想，但通过容量缩放技术提高了效率。
问题描述
给定一个有向图G=(V,E)，其中V是顶点集合，E是边集合。每条边(u,v)∈E有一个非负容量c(u,v)≥0。指定一个源点s∈V和一个汇点t∈V。最大流问题是寻找从s到t的最大流量，满足：
- 容量约束：对于所有边(u,v)，流量f(u,v)≤c(u,v)
- 流量守恒：对于所有顶点u≠s,t，流入u的流量等于流出u的流量
解题过程
第一步：理解容量缩放的基本思想
容量缩放算法的核心思想是逐步改进流值。我们不是一次增加1个单位的流量，而是先考虑较大的容量增量Δ，然后逐步减小Δ，直到Δ=1。
- 初始时，设Δ为不大于最大容量的最大2的幂次
- 在每轮迭代中，只考虑剩余容量至少为Δ的边
- 当找不到增广路径时，将Δ减半
第二步：算法初始化
考虑一个具体实例：
顶点：{s, a, b, c, d, t}
边及其容量：
s→a: 10, s→b: 10
a→b: 2, a→c: 8, a→d: 4
b→d: 9
c→t: 10
d→c: 6, d→t: 10
初始化步骤：
- 初始流f(u,v)=0，对所有边(u,v)
- 计算初始Δ = 2^⌊log₂(max capacity)⌋ = 2^⌊log₂(10)⌋ = 2³ = 8
- 构建剩余图G_f，其中剩余容量r(u,v)=c(u,v)-f(u,v)+f(v,u)
第三步：第一轮缩放（Δ=8）
在当前剩余图中，只考虑剩余容量r(u,v)≥8的边：
- s→a: r=10≥8 ✓
- s→b: r=10≥8 ✓
- a→c: r=8≥8 ✓
- c→t: r=10≥8 ✓
- d→t: r=10≥8 ✓
寻找增广路径：s→a→c→t，瓶颈容量min(10,8,10)=8
增加流量8：
- f(s,a) += 8
- f(a,c) += 8
- f(c,t) += 8
当前总流量=8
第四步：第二轮缩放（Δ=8继续）
更新剩余图后，仍考虑r(u,v)≥8的边：
- s→b: r=10≥8 ✓
- 其他边剩余容量均<8
寻找增广路径：s→b→d→t，但b→d剩余容量=9≥8 ✓，d→t剩余容量=10≥8 ✓
路径s→b→d→t，瓶颈容量min(10,9,10)=8
增加流量8：
- f(s,b) += 8
- f(b,d) += 8
- f(d,t) += 8
当前总流量=16
第五步：Δ减半（Δ=4）
在剩余容量r(u,v)≥4的边中寻找增广路径：
剩余边包括：
- s→a: r=2<4 ✗
- s→b: r=2<4 ✗
- a→b: r=2<4 ✗
- a→c: r=0<4 ✗
- a→d: r=4≥4 ✓
- b→d: r=1<4 ✗
- c→t: r=2<4 ✗
- d→c: r=6≥4 ✓
- d→t: r=2<4 ✗
找不到从s到t的路径，Δ再次减半。
第六步：Δ=2
考虑剩余容量r(u,v)≥2的边：
- s→a: r=2≥2 ✓
- s→b: r=2≥2 ✓
- a→b: r=2≥2 ✓
- a→d: r=4≥2 ✓
- d→c: r=6≥2 ✓
- c→t: r=2≥2 ✓
- d→t: r=2≥2 ✓
找到增广路径：s→a→d→c→t
瓶颈容量min(2,4,6,2)=2
增加流量2：
- f(s,a) += 2
- f(a,d) += 2
- f(d,c) += 2
- f(c,t) += 2
当前总流量=18
第七步：Δ=1及最终优化
继续使用更小的Δ值，直到Δ=0.5时结束。最终找到最大流为19。
算法复杂度分析
- 每轮缩放阶段最多找O(|E|)条增广路径
- 缩放次数为O(log C)，其中C是最大容量
- 总复杂度：O(|E|² log C)
容量缩放算法通过优先处理高容量边，减少了寻找增广路径的次数，相比基本的Ford-Fulkerson方法有更好的理论保证。