最大流算法

最大流问题是指在一个有向图中,每条边的容量有限,求两点间能通过的最大流量。解决此问题常用Ford–Fulkerson方法,本文对此方法做一总结记录。

在最大流问题中,涉及到很多术语,如残留网络、增广路径等,本文不打算使用和介绍这些名词,想深入了解此问题的话可进一步阅读文末的参考资料,这里仅从编程使用的角度介绍算法实现方法。

Ford–Fulkerson方法的基本步骤很简单:

  1. 在当前的图中寻找任意一条从源点到汇点的路径;
  2. 为这条路径添加一条反向路径;
  3. 重复以上两步,直至无法找到更多的路径为止。

这个算法如此简单,很让人怀疑其正确性,不过,根据最大流与最小割定理,我们可以严格的证明:只要每一条边的容量都是有理数,Ford–Fulkerson方法肯定收敛于图的最大流,然而,若容量是无理数,算法不一定会收敛。证明步骤可以参考第二篇参考资料。

算法的执行过程可以参考这个动画演示

此方法之所以称为Ford–Fulkerson方法而不是Ford–Fulkerson算法的原因在于,第一步寻找路径的过程可以使用很多不同的策略,这就可以衍生出各种不同的具体实现算法,其中最常用的一种是使用BFS广度优先搜索策略,这种算法称之为Edmonds-Karp算法。最后一篇参考资料中给出了一个实现代码,此处给出另一种封装更好一些的实现代码,实用邻接表实现。


图的相关数据结构定义:

1
2
3
4
5
6
7
8
9
10
11
typedef struct _path {
int dst;
int flow;
} path;

typedef struct _vertex {
list<path> adjacency; // 邻接表
bool visited; // BFS搜索记录
int pre; // 前一个节点
int minflow; // 当前路径流量
} vertex;

FindPath()函数使用BFS搜索srcdst之间的一条路径,并计算此条路径的流量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool FindPath(vector<vertex> & G, int src, int dst) {
deque<int> buf;
buf.push_back(src);

while (!buf.empty()) {
int s = buf.front();
buf.pop_front();

G[s].visited = true;
if (s == dst)
return true;

// 更新与G[s]节点相连的所有节点的状态
for (auto it = G[s].adjacency.begin(); it != G[s].adjacency.end(); it++) {
// 未访问过且有剩余流量
if (!G[it->dst].visited && it->flow > 0) {
G[it->dst].pre = s;
G[it->dst].minflow = it->flow < G[s].minflow ? it->flow : G[s].minflow;
buf.push_back(it->dst);
}
}
}
return false;
}

AddFlow()函数更新流量信息(减去正向流量并添加反向流量),返回值即为当前路径流量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int AddFlow(vector<vertex> & G, int src, int dst) {
int v = dst;
int minflow = G[v].minflow;
while (v != src) {
for (auto it = G[v].adjacency.begin(); it != G[v].adjacency.end(); it++) {
if (it->dst == G[v].pre) {
it->flow += minflow;
break;
}
}
for (auto it = G[G[v].pre].adjacency.begin(); it != G[G[v].pre].adjacency.end(); it++) {
if (it->dst == v) {
it->flow -= minflow;
break;
}
}
v = G[v].pre;
}
return minflow;
}

GClear()函数用于清除上一次BFS的中间数据,为下一次循环做好准备:

1
2
3
4
5
6
7
void GClear(vector<vertex> & G) {
for (auto it = G.begin(); it != G.end(); it++) {
it->visited = false;
it->minflow = INT_MAX;
it->pre = -1;
}
}

最后是测试用的main()函数:

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
int main() {
int V,E;
cout << "V, E : ";
cin >> V >> E;
vector<vertex> G = vector<vertex>(V);

GClear(G);
while (E--) {
int s, d, f;
cin >> s >> d >> f;
G[s].adjacency.push_back((path){d, f});
G[d].adjacency.push_back((path){s, 0}); // 反向流量初始值为0
}

int src, dst;
cout << "src, dst: ";
cin >> src >> dst;

int flow = 0;
while (FindPath(G,src,dst)) {
flow += AddFlow(G, src, dst);
GClear(G);
}

cout << "MaxFlow: " << flow << endl;
return 0;
}

参考资料:
算法导论(Introduction to Algorithm)第26章 最大流
6.854 高级算法 —— 网络流 最大流
最大流(一)