210
8
8.2.1 输入 / 输出
对于
E
中的每条边
(
u, v
)
Ford-Fulkerson
算法会计算出整数流量
f
(
u, v
)
,用于表示流
经边
(
u, v
)
的单位流量。算法在结束时,还会顺道计算出网络的最小割,即由边集
组成一个“瓶颈”,来防止更多的单元在网络中从
s
流向
t
8.2.2 决方案
这里介绍的
Ford-Fulkerson
算法实现采用了链表存储边。每个顶点
u
维护着两个不同
的列表:从
u
发出的前向边和指向
u
的后向边,因此每条边都会在这两个列表中出现
本书的代码库中包含了一个使用二维数组存储边的算法实现,这个数据结构更适用于稠
密的流网络图。
Ford-Fulkerson
算法
依赖于如下结构:
FlowNetwork
代表网络流问题。这个抽象类有两个子类一个基于邻接表,另一个基于邻接矩阵。
getEdgeStructure()
法会返回边集的底层存储结构。
VertexStructure
为顶点维护两个链表(前向和后向),分别为从顶点离开的边和进入顶点的边。
EdgeInfo
在网络流中记录边的信息。
VertexInfo
记录搜索到的增广路径。
VertexInfo
会记录增广路径之前的顶点,以及它是被前向
边还是后向边访问到的。
Ford-Fulkerson 算法小结
最好情况、平均情况和最坏情况:
O
(
E
*
mf
)
compute (G)
while exists augmenting path in G do
processPath (path)
end
processPath (path)
v = sink
delta =
while v
source do
u = vertex previous to v in path
if edge(u,v) is forward then
网络流算法
211
网络流算法
t = (u,v).capacity - (u,v).flow
else
t = (v,u).flow
delta = min (t, delta)
v = u
v = sink
while v
source do
u = vertex previous to v in path
if edge(u,v) is forward then
(u,v).flow += delta
else
(v,u).flow -= delta
v = u
end
循环上限次数为
mf
,这使得总体性能为
O
(
E*mf
)
从后往前由
汇点
出发寻找最小的能够潜在增加流量的边。
相应地调整增广路径。
前向边增加流量,后向边减少流量。
8-1
给出了
Ford-Fulkerson
算法的实现,其流程如图
8-3
所示。其中,
Search
对象
可以进行配置,它可以用于计算出网络中的增广路径,并且在不违反容量限制准则的前
提下向网络中加入更多的流。如果在之前迭代的过程中做出的是次优决定,那么
Ford-
Fulkerson
算法会继续进行搜索并且不需要撤销之前的工作。
8-1
Ford-Fulkerson
算法的
Java
示例实现
public class FordFulkerson {
FlowNetwork network; /**
代表流网络问题。
*/
Search searchMethod; /**
将要使用的搜索方法。
*/
//
构造一个实例,来计算指定网络上的最大流,
//
使用
searchMethod
寻找增广路径。
public FordFulkerson (FlowNetwork network, Search method) {
this.network = network;
this.searchMethod = method;
}
//
计算流网络上的最大流。计算结果存储在流网络对象中。
public boolean compute () {
boolean augmented = false;
while (searchMethod.findAugmentingPath(network.vertices)) {
processPath(network.vertices); augmented = true;
}
return augmented;
}
212
8
//
寻找一条可扩展流的最小的边,然后更新源点到汇点的流。
protected void processPath(VertexInfo []vertices) {
int v = network.sinkIndex;
int delta = Integer.MAX_VALUE; //
目标是找到最小的
while (v != network.sourceIndex) {
int u = vertices[v].previous;
int flow;
if (vertices[v].forward) {
//
利用边的剩余容量调整前向边。
flow = network.edge(u, v).capacity - network.edge(u, v).flow;
} else {
//
根据
现有的流减少后向边。
flow = network.edge(v, u).flow;
}
if (flow < delta) { delta = flow; } //
更小的
待选流。
v = u; //
按照反向路径寻找源
点。
}
//
根据
delta
调整路径(增加前向边流量,减少后向边流量)。
v = network.sinkIndex;
while (v != network.sourceIndex) {
int u = vertices[v].previous;
if (vertices[v].forward) {
network.edge(u, v).flow += delta;
} else {
network.edge(v, u).flow -= delta;
}
v = u; //
按照反向路径寻找源
点。
}
Arrays.fill(network.vertices, null); //
清空中间结果,进行下一次迭代。
}
}
在图
8-5
,任何扩展自抽象
Search
类的搜索方法都能够用于寻找增广路径
Ford-
Fulkerson
算法的原始版本采用的是
深度优先搜索
(见图
8-4
,而
Edmonds-Karp
法采用的是
广度优先搜索
(见第
6
章)。
8-3
中的流网络示例展示了采用
深度优先搜索
寻找增广路径的结果,
8-2
是其实现。
路径使用栈存储顶点。增广路径采用如下方式不断扩展:首先从栈中弹出一个顶点
u
然后找到
u
的一个未访问的邻接顶点
v
,顶点
v
需要满足两个条件:①边
(
u
,
v
)
是一条前
向边并且还有多余的容量,②边
(
v
,
u
)
是一条后向边,并且通过此边的流可以减少。如
果存在这样的顶点,那么就将
v
添加到路径的末尾,并继续执行内部的
while
循环。最终,
要么访问到了汇点
t
,要么路径为空,即表示再也找不到增广路径了。
网络流算法
213
网络流算法
8-3Ford-Fulkerson 算法示例
214
8
8-4Ford-Fulkerson 算法的建模信息
8-5Search 的功能
8-2
:使用深度优先搜索寻找增广路径
public boolean findAugmentingPath (VertexInfo[] vertices) {
//
从源
点开始寻找增广路径。
vertices[sourceIndex] = new VertexInfo (-1);
Stack<Integer> path = new Stack<Integer>();
path.push (sourceIndex);
//
处理
u
的前向边,然后再处理后向边。
VertexStructure struct[] = network.getEdgeStructure();
while (!path.isEmpty()) {
int u = path.pop();
//
首先处理前向边。
Iterator<EdgeInfo> it = struct[u].forward();
while (it.hasNext()) {
EdgeInfo ei = it.next();
int v = ei.end;
//
如果还没有访问,并且有剩余容量,那么就准备增加流。

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.