最大流算法

发表于   |  

定义

设给定边容量为CV,W的有向图G=(V,E)。这些容量可以代表一个管道的水的流量或者两个交叉路口之间马路上的交通流量。
有两个定点，一个是s，成为源点，一个是t，成为汇点。对于任意条边(v,w)，最多有CV,W个单位的“流”可以通过。
最大流问题就是确定从s到t可以通过的最大流量。

性质和重要概念

一个合法的网络流有以下三大性质，其中f[u,v]表示结点u到v的当前流量，c[u,v]表示结点u到v的最大流量

  1. 容量限制：f[u,v] <= c[u,v]
  2. 反对称性：f[u,v] = -f[v,u]
  3. 流量守恒：对于不是源点也不是汇点的任意结点，流入该结点的流量和等于流出该结点的流量和

重要概念

我们从图G开始构造一个流图Gf，表示在算法的任意阶段已经达到的流。
再构造一个图Gr，称为残余网络（残余图），表示对于每条边还能添加上多少流。
在每个阶段，在图Gr中寻找一条从s到t的路径，称为增广路径。
显然，G = Gr + Gf

反向边：假设从a到b的最大流量为10,现在添加一条从a到b负载为10的流量，与此同时，产生一条从b到a流量为10的反向边。
然后发现，这不是最优解，可以把其中的4份流量从a流向其他结点，以达到更优解，于是可以添加一条从b到a负载为4的流量。
所以，反向边的作用就是给算法一个可以反悔修正的机会。

最大流定理：如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。

算法

tle Ford–Fulkerson algorithm DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * nodes：网络的结点数
 * edges：网络的边数
 * s, t：分别为所求最大流的起点和终点
 * network：邻接矩阵表示网络中当前的剩余流量
 */
int nodes, edges;
int s, t;			// from 0 on
int [][] network;	// from 0 on

/**
 * flow：网络中的最大流量
 * path：用数组表示每次寻找到的增广路径，初值为-1，长度为结点数(nodes)
 * 若能够在残余网络中(即network)通过DFS找到一条增广路径，则流量增加，然后更新残余网络
 * 直到不能找到一条增广路径，根据最大流最小割原理，当前flow即为最大流量
 * @return flow
 */
private int maxflow() {
	int flow = 0;
	int [] path;	//寻找一条增广路径
	
	while (true) {
		path = new int [nodes];
		
		if (dfs(path) == false) break;
		int min = Integer.MAX_VALUE / 2;
		for (int i = 0; i < nodes-1; i++) {
			if (path[i+1] == -1) break;
			min = Math.min(min, network[path[i]][path[i+1]]);
		}
		
		flow += min;
		for (int i = 0; i < nodes-1; i++) {
			if (path[i+1] == -1) break;
			network[path[i]][path[i+1]] -= min;
			network[path[i+1]][path[i]] += min;
		}
	}
	
	return flow;
}

/**
 * 以非递归的方式进行DFS，使用数组模拟栈
 * vis：用于标记访问过的结点
 * flag：用于回溯
 * 每次取path中最新的结点，若它为终点t，即找到了一条增广路径
 * @param path：用于存储一条增广路径，每次dfs操作都赋初值-1
 * @return 若能找到一条增广路径，返回true，否则返回false
 */
private boolean dfs(int [] path) {	// assume s != t
	boolean [] vis = new boolean [nodes];
	boolean flag;
	int n = 0, u;
	
	path[n++] = s;
	for (int i = 1; i < nodes; i++) {
		path[i] = -1;
	}
	
	while (n > 0) {
		u = path[n-1];
		if (u == t) return true;
		vis[u] = true;
		flag = true;
		for (int i = 0; i < nodes; i++) {
			if (network[u][i] > 0 && !vis[i]) {
				path[n++] = i;
				flag = false;
				break;
			}
		}
		if (flag) path[--n] = -1;
	}
	
	return false;
}