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.