作者：禅与计算机程序设计艺术
1.背景介绍
最大流（Max Flow）问题是一种在图论中的经典问题，它属于网络流问题，指的是某条流量限制下的流网络中从一个源点到达另一个汇点可获得的最大流量。给定一个有向图G=(V,E),其中每条边(u,v)∈E有一个非负容量c(u,v)，且源点s和汇点t存在。最大流问题通常可以用Ford-Fulkerson方法求出。在本文中，我们将阐述最大流问题的定义、性质、关键思想以及Ford-Folkerson方法。
2.核心概念与联系
2.1 定义与性质
（1）定义
最大流问题是在图论里的一类问题。给定一个有向图$G = (V, E)$，其中每条边$(u, v) \in E$有正权值$c_{uv} > 0$,且$s\in V, t\in V$是它的源点和汇点。流网络$G$上任意一条从$s$到$t$的路径称为流，若两个流之间没有边相连接，则这两条流相交称为割；流的值是指从源点$s$通过所有割可达的流的总和。对于流网络$G$而言，如果存在着一条从$s$到$t$的路径上的流，那么就称该流网络为流网络；否则，该网络不具有流。
（2）性质
最大流问题的几何解释如下：给定一幅画布，画一个圆圈并用箭头把它连起来，圆圈所在位置即为源点，边界外位置即为汇点。圆圈内的区域即为能够通过流路传输水的地方。当引力作用下，这些区域中的物体会发生漩涡，而通过集中力的作用，这些漩涡便会被流线所抑制。这个过程叫做对偶性质：容量约束的作用使得流不能无限增加，反之亦然，因此，流仅能沿着最短路径增长。为了衡量流网络中实际可实现的最大流量，可以测量流网络中流过的物体数量。
最大流问题的两个基本性质：
- 残留网络（Residual network）: $G_f$是一个残留网络，它是流网络$G$中，从源点$s$到汇点$t$的各个边的剩余容量$c_{uv}-f_{uv}$组成的子图。残留网络$G_f$必须是强连通的。
- 割的性质（Cut property）：设流网络$G$的流值为$f=f_{st}$。如果$G$中存在从源点$s$到汇点$t$的路径$\pi={s,\cdots,t}$,并且$e_{ij}\notin \delta^+(i)$,其中$\delta^+(i)$表示$i$的所有邻接节点（包括$i$自身），则称$\pi$为割。证明：设$\lambda$是容量函数，则$f_{\pi}=c_{\pi}+\sum_{i<j}(1-\lambda(\pi, e_{ij}))f_{ij}$.因此，当容量约束$\leq f_{\pi}$满足时，$\lambda(\pi, e_{ij})=1$.
（3）Ford-Folkerson方法
Ford-Folkerson方法是一种迭代的方法，它利用容量约束和对偶性质计算最大流。Ford-Folkerson方法的基本思想是：每一次迭代都把流往前推，直至可以找到一条增广路径；如果找不到这样的路径，则停止算法。Ford-Folkerson方法求得的最大流就是整个网络中可得到的最大流。
2.2 关键思想
最大流问题的关键思想有三点：
- 流网络表示法：把流网络$G=(V,E)$表示为残留网络$G_f=(V,E^\prime)$。残留网络中每条边$(u,v)\in E^\prime$代表着从源点$s$到汇点$t$之间能够承载的最大流量。利用容量约束和流方向，残留网络中的每个节点都对应着一个容量，残留网络中一条边$(u,v)$的容量等于它在$G$中的流量减去它在$G_f$中的流量。如果残留网络中的某个边的容量小于或等于0，则意味着流不能流入节点u。如果某个节点的入度等于其出度，则意味着这个节点处于饱和状态，流无法再从这个节点进入。
- 对偶性质：Ford-Folkerson方法中使用的就是对偶性质，它告诉了如何在残留网络中计算最大流。首先，Ford-Folkerson方法选择一个节点$x$，通过它可以增大流。对于节点$x$，Ford-Folkerson方法寻找一条从源点$s$到$x$的路径$\pi={s,\cdots,x}, x\neq s$，然后把$\pi$上所有的容量都减掉。如果所有边的容量都不为负数，并且在节点$x$处不会出现死循环，则说明流已经到达了节点$x$。这时，需要把节点$x$上的流加入到其它的残留网络节点上，继续寻找增广路径。如此重复直到所有节点都可以接收流。Ford-Folkerson方法的算法描述如下：
- 初始化：令所有边的容量都为正整数，$G_f=(V,E^\prime)$初始化为空，残留网络$G_f$表示源点到其他各个顶点的边以及这些边的容量。令$f_{s}=0$，其它初始流量都为0。
- 当$|f_{s}|>|c_{s,v}|$, 其中$v\in N(s)$，则令$f_{sv}=c_{sv}-f_{s}$，其中$N(s)$表示节点$s$的所有邻接点。否则，选择一个节点$v$，$f_{sv}$表示从源点$s$到节点$v$的流量，如果$f_{sv}>0$则加入$E_f$。
- 如果$E_f$中所有的容量都为负数，或者流量不能从源点$s$流出，则停止算法。否则，返回第2步。
- 求解目标函数：目标函数是所有边的流量的总和：$\min{c_{uv}-f_{uv}}$，其中$c_{uv}-f_{uv}=0$当且仅当节点$u$与节点$v$可以互相通信，即$u$的出度等于其入度。由于容量约束，$c_{uv}-f_{uv}\geqslant 0$，因此只需要计算所有容量为正值的边的流量${f_{uv}}$就可以求得目标函数。当所有边的流量都为0时，最大流也就得到了。
3.核心算法原理和具体操作步骤以及数学模型公式详细讲解
3.1 理解最大流网络的表示方法
对于任意一个图，都存在两种不同的表示方式：稀疏矩阵表示和邻接表表示。然而，图论里的很多问题，比如最大流问题，都可以由稠密图的邻接表表示简化。在这种情况下，每条边就代表着一个结点之间的流量，流量的大小就代表着两个结点间的距离。所以，对于任意一个有向图$G=(V,E)$，均可以使用邻接表表示其对应的流网络$G_f=(V,E^\prime)$，其中$E^\prime$由所有具有非负容量的边$(u,v)$组成。用邻接表表示流网络$G_f$非常简单：在邻接表$Adj[u]$中存储所有结点$u$的邻居结点，每个邻居结点及其关联的边容量。另外，还可以额外维护一个数组$excess[v]$，用于存储结点$v$的余流量。余流量表示从源点$s$到结点$v$的流量，如果一个结点$v$的出度大于入度，那么$excess[v]<0$，否则$excess[v]>0$。下面来看具体的代码实现。
class Edge:
def __init__(self, v, cap):
self.v = v # 邻居结点
self.cap = cap # 容量
self.flow = 0 # 当前流量
def maxFlow(graph, s, t):
n = len(graph)
INF = float('inf')
dist = [INF] * n # 从s到各个顶点的距离
prev = [-1] * n # 上一个顶点
edge = [[None for _ in range(n)] for _ in range(n)] # 邻接表
# build graph
for u in range(n):
for v, w in graph[u]:
if not edge[u][v]:
edge[u][v] = Edge(v, w)
else:
assert False, "Multiple edges"
while True:
q = [] # BFS queue
# bfs from s to find shortest augmenting path
dist[s] = 0
push(q, s)
while q and dist[t] == INF:
u = pop(q)
if excess[u] <= 0:
continue
for e in adj[u]:
if not edge[u][e.v]:
continue
df = min(excess[u], e.cap - e.flow)
if dist[e.v] > dist[u] + df:
dist[e.v] = dist[u] + df
prev[e.v] = u
if e.v!= t:
push(q, e.v)
if dist[t] == INF:
break
flow += excess[t]
v = t
while v!= s:
u = prev[v]
edge[u][v].flow += excess[t]
edge[v][u].flow -= excess[t]
v = u3.2 Ford-Folkerson方法
Ford-Folkerson方法的基本思想是：利用残留网络来计算最大流。每次迭代，找到一个增广路径，然后更新流。如果找不到这样的路径，则停止算法。增广路径的产生是一个重要的性质。举例来说，对于图中图示的网络，如果有$s-a-b$和$s-d$两条增广路径，那么只有$s-d$是最大流的增广路径。在这种情况下，Ford-Folkerson方法每次只增加一条增广路径，而不是同时增加两条增广路径。
Ford-Folkerson方法构造了容量为正的边的集合$E^\prime$。对于边$(u,v)$，如果残留网络中没有相关的边，则创建一个新的边$(u,v)$，否则，就把容量加到相应的边上。如果边$(u,v)$容量变为0，则从节点$u$删除它的邻接边，以及$u$到其它节点的相应的边。
while True:
addEdgs(G) # 添加新的容量为正的边
foundAugPath = false
Q = G.vertices() # 队列
pred[s] = None
while Q is not empty and!foundAugPath:
u = dequeue(Q)
for e in Adj[u]:
v = e.dest
if residualCapacity(e) > 0 and v!= s and pred[v] is None:
pred[v] = u
if v == t or depthFirstSearch(v, t, pred):
return true
enqueue(Q, v)
// 不存在增广路径
return false;
// 深度优先搜索
boolean depthFirstSearch(int u, int target, vector<int>& pred):
stack<int> S;
S.push(u);
while (!S.empty()) {
u = S.top();
S.pop();
if (u == target)
return true;
for (edge e : adj[u]) {
v = e.dest;
if (residualCapacity(e) > 0 && pred[v] is null) {
pred[v] = u;
S.push(v);
}
return false;
}3.3 重建网络与最短增广路径
Ford-Folkerson方法计算完最大流后，不能直接回答流的问题。但是，可以通过重建网络来获取流的信息。首先，要用最短增广路径回溯网络中每条边的实际流量。最短增广路径就是一条通过最小的边数从源点到汇点的路径。Ford-Folkerson方法中也采用了深度优先搜索，根据搜索树的最后一个访问的节点作为增广路径的起点。用栈$stack$来记录搜索顺序。
vector<pair<int, int>> parent; // 记录增广路径的父亲结点
parent.resize(n+1);
for i in range(n+1):
parent[i] = {-1, -1}; // 默认值设置为空
function rewind():
int p = top;
currNode = parent[p].first;
for each node p's father:
currEdge = (currNode, p);
capacity = getEdgeCap(currEdge);
flow = getEdgeFlow(currEdge);
setEdgeFlow(currEdge, capacity - flow);
while currNode!= s:
parent[prevNode] = make_pair(currNode, currEdge);
prevNode = currNode;
currNode = parent[currNode];
if source!= sink: // 检查是否有环路，如果有就不存在增广路径
cout << "No augmenting path.\n";
exit(0);
else: // 有增广路径
cout << "The maximum flow is:\n";
printMaxFlow();
void dfsShortestPaths():
visited[source] = true;
S.push({source, 0}); // 放入到栈中，注意这里的cost要设置为0
while S is not empty:
u = S.top().node; // 从栈中取出一个结点
c = S.top().cost; // 取出栈中结点的cost
S.pop(); // 删除栈中结点
if visited[u]: // 跳过已经访问过的结点
continue;
for each neighbor v of u:
if visited[v]: // 只处理没访问过的邻接点
continue;
relax(u, v, c);
if v!= sink:
visited[v] = true;
S.push({v, d[v]}); // 更新dist信息，放入栈中，注意这里的dist是结点u到sink的cost
void relax(u, v, c):
if weight(u, v) == inf || d[v] > d[u] + weight(u, v):
d[v] = d[u] + weight(u, v);
pred[v] = u;
if v!= source: // 更新增广路径
reverse(adj[u]);
int i = lowerBound(adj[u], v);
swap(adj[u][i-1], adj[u][i]);
reverse(adj[u]);
updateParent(u, v, c);