本文参考以下文章
Flow Networks 基本性质展开目录
在图论中，网络流被定义为一个有向图，其中包含一个起点 Source 和一个终点 Target，以及几条连接各顶点的边。每条边都有各自的容量 Capacity，这是边所能允许的最大流量
网络流中的流量 $f$ 应满足如下条件
- 从节点 $x$ 流向节点 $y$ 的流量，不能比 $edge (x,y)$ 的 capacity 还大，$f (x,y)≤c (x,y)$
- 若定义 从节点 $x$ 流向节点 $y$ 的的流量有 5 单位，$f (x,y)=5$，则 从节点 $y$ 流向节点 $x$ 的流量有 - 5 单位，$f (y,x)=-5$
对图中除了 Source 和 Target 以外的结点，所有输入的流量之和要等于所有输出的流量之和
- 也就是流量不会无故增加或无故减少，可视为一种能量守恒
- 以下图为例，流入节点 A 的流量为 6，流出的流量也是 6，对 C、D 也是
最大流：网络允许从源 Source 流向终点 Target 的最大流量
下面介绍 Ford-Fulkerson Algorithm（若使用 BFS，则又称为 Edmonds-Karp Algorithm）来解决此问题
Ford-Fulkerson Algorithm展开目录
Ford-Fulkerson Algorithm 需要两个辅助工具
- Residual Networks（残差网络）
- Augmenting Paths（增广路径）
Residual Networks展开目录
残差网络表示图中每条边剩余可允许通过的流量构成的图，以下图为例
若在 Path：S-A-C-D-T 上的所有边都有 6 单位的流量，那么这些边，$edge (S,A)$、$edge (A,C)$、$edge (C,D)$、$edge (D,T)$ 的剩余容量都应该减 6。例如，$edge (S,A)$ 只能容纳 3 单位的流量，$edge (C,D)$ 只能容纳 1 单位的流量
若 $edge (x,y)$ 上有 $f (x,y)$ 单位的流量流过，则 $edge (x,y)$ 上的 residual capacity 定义为：
$c_f(x,y)=c(x,y)-f(x,y)$
- $c (x,y)$ 为原始 edge (x,y) 的容量
- $f (x,y)$ 表示目前 edge (x,y) 已有多少流量
- $c_f (x,y)$ 表示 edge (x,y) 还能容纳多少流量
Residual Networks 也是一个有向图，其中：
- 顶点集与原有向图完全相同
- 边的容量被 residual capacity 取代，如下图所示
最关键的是，若 $edge (A,C)$ 上有 6 单位的流量流过 $f (A,C)=6$，那么在其 Residual Networks 上，会相应产生出一条顶点 C 指向顶点 A 的边 $edge (C,A)$，并具有 6 单位的 residual capacity$c_f(C,A)=6$
这样做有什么意义？可以用如果想要重新配置流量方向来理解
举例来说，假设现在恢复到初始状态（没有任何流量流过），现在有 2 单位的流量经过 Path：S-C-A-B-T，但是由于并不存在从顶点 C 指向顶点 A 的 $edge (C,A)$，因此 $c (C,A)=0$。假设有 6 单位的流量从顶点 A 流向顶点 C（如上图所示），那么现在就可以从 $edge (A,C)$ 上把 2 单位的流量收回，从而分配到 $edge (A,B)$ 上，而 $edge (A,C)$ 上，就只剩下 4 单位的流量，最后结果如下图左所示，此时的 Residual Networks 如下图右所示
下图是从网上找到的另一个例子
Augmenting Paths展开目录
在 Residual Networks 里，所有能够从源 Source 走到终 Target 的路径，也就是所有能够增加流量的路径，就称为 Augmenting Paths（增广路径）
以上图为例，Augmenting Paths 有很多种可能，例如
Path：S-A-B-T，1~3 单位的流量
- 因为在该路径中，所有 edge 中最小的 capacity 为 $c (S,A)=c (A,B)=3$，因此可以容许流量大小为 1~3
Path：S-C-B-D-T，1~2 单位的流量
- 因为在该路径中，所有 edge 中最小的 capacity 为 $c (B,D)=c (D,T)=2$，因此可以容许的流量大小为 1~2
综上
若要看当前流入 Target 的总流量，要在下图左，edge 上标示
flow/capacity的图上找- 下图左流入终点 Target 的 flow 为 8 单位
若要找还能增加多少流量，也就是找 Augmenting Paths，需要在 Residual Networks 上找，如下图右所示
- 若在 Path：S-A-B-T、Path：S-A-C-D-T、Path：S-C-B-T 流入不超过该路径上最低 residual capacity 的 flow， 都是 Augmenting Paths
讲完上面两个概念，下面讲解 Ford-Fulkerson Algorithm 算法
在 Residual Networks 上寻找 Augmenting Paths
- 以
BFS()寻找，确保每次找到的 Augmenting Paths 一定经过最少的 edge - 找到 Augmenting Paths 上最小的 residual capacity，将其加入总 flow
- 再以最小的 residual capacity 更新 Residual Networks 上 edge 的 residual capacity
- 以
- 重复上述步骤，直到再也没有 Augmenting Paths 为止
以上图为例，寻找 Maximum Flow 的步骤如下
- 开始时用
flow = 0初始化 residual Networks
在图中，以
bfs()找到从 S 到 T 且 edge 最少的 Path：S-A-B-Tbfs()找到的可能有三条最短 Path，这里就以 S-A-B-T 为例
- 观察 Path：S-A-B-T 上的 edge，发现 $edge (A,B)$ 具有最小的 residual capacity $c_f (A,B)=3$，所以 update：总 flow 增加 3
更新 edge 的 residual capacity
- $c_f(S,A)=c(S,A)-f(S,A)=9-3=6$
- $c_f(A,S)=c(A,S)-f(A,S)=0+3=3$
- $c_f(A,B)=c(A,B)-f(A,B)=3-3=0$
- $c_f(B,A)=c(B,A)-f(B,A)=0+3=3$
- $c_f(B,T)=c(B,T)-f(B,T)=9-3=6$
- $c_f(T,B)=c(T,B)-f(T,B)=0+3=3$
- 在途中，以
bfs()找到从 S* 到 T 且 edge 最少的 Path：S-C-D-T
- 观察 Path：S-C-D-T 上的 edge，发现 $edge (C,D)$ 具有最小的 residual capacity $c_f (C,D)=7$，所以 update：总 flow 增加 7
更新 edge 的 residual capacity
- $c_f(S,C)=c(S,C)-f(S,C)=9-7=2$
- $c_f(C,S)=c(C,S)-f(C,S)=0+7=7$
- $c_f(C,D)=c(C,D)-f(C,D)=7-7=0$
- $c_f(D,C)=c(D,C)-f(D,C)=0+7=7$
- $c_f(D,T)=c(D,T)-f(D,T)=8-7=1$
- $c_f(T,D)=c(D,T)-f(T,D)=0+7=7$
接着重复上述步骤：更新 Residual Networks，寻找 Augmenting Paths
- 找到 Path：S-C-B-T
- 更新 Residual Networks
- 找到 Path：S-A-C-B-T
- 更新 Residual Networks
- 找到 Path：S-A-C-B-D-T
- 更新 Residual Networks
- 找到 Maximum Flow=17
完整代码如下
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
-
- class Graph {
- private:
- int num_vertex; //顶点
- vector<vector<int>> map; // 邻接矩阵
- public:
- Graph():num_vertex(0){};
- Graph(int n);
- void AddEdge(int from, int to, int capacity);
- void FordFulkerson(int s, int t);
- bool BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t);
- int MinCapacity(vector<vector<int>> graph, int* predecessor, int t);
- };
-
- Graph::Graph(int n):num_vertex(n) {
- map.resize(num_vertex);
- for (int i = 0; i < num_vertex; i++)
- map[i].resize(num_vertex);
- }
-
- bool Graph::BfsFindExistingPath(vector<vector<int>> graph, int* predecessor, int s, int t) {
- int visited[num_vertex];
- for (int i = 0; i < num_vertex; i++) {
- visited[i] = 0; // 0 表示没有访问过
- predecessor[i] = -1;
- }
-
- queue<int> queue;
- queue.push(s);
- visited[s] = 1; // 1 表示访问过
- while (!queue.empty()) {
- int vertex = queue.front(); queue.pop();
- for (int j = 0; j < num_vertex; j++) {
- if (graph[vertex][j] != 0 && visited[j] == 0) {
- queue.push(j);
- visited[j] = 1;
- predecessor[j] = vertex;
- }
- }
- }
- return (visited[t] == 1); // 若t被访问过，表示有path从s到t
- }
-
- int Graph::MinCapacity(vector<vector<int>> graph, int* predecessor, int t) {
- int min = 0x3f3f3f; // 确保min会更新，假设graph上的capacity都小于0x3f3f3f
-
- // 用predecessor[idx]和idx表示一条edge
- // 找到 从s到t 的path中，capacity最小的值，存入min
- for (int idx = t; predecessor[idx] != -1; idx = predecessor[idx])
- if (graph[predecessor[idx]][idx] != 0 && graph[predecessor[idx]][idx] < min)
- min = graph[predecessor[idx]][idx];
- return min;
- }
-
- void Graph::FordFulkerson(int s, int t) {
- vector<vector<int>> graphResidual(map);
- int maxflow = 0;
- int predecessor[num_vertex];
-
- // bfs find augmeting path
- while (BfsFindExistingPath(graphResidual, predecessor, s, t)) {
- int min_capacity = MinCapacity(graphResidual, predecessor, t);
- maxflow = maxflow + min_capacity;
- for (int y = t; y != s; y= predecessor[y]) {
- // update residual graph
- int x = predecessor[y];
- graphResidual[x][y] -= min_capacity;
- graphResidual[y][x] += min_capacity;
- }
- }
- cout << "Maximum Flow: " << maxflow << endl;
- }
-
- void Graph::AddEdge(int from, int to, int capacity) {
- map[from][to] = capacity;
- }
-
- int main() {
- Graph g(6);
- g.AddEdge(0, 1, 9);g.AddEdge(0, 3, 9);
- g.AddEdge(1, 2, 3);g.AddEdge(1, 3, 8);
- g.AddEdge(2, 4, 2);g.AddEdge(2, 5, 9);
- g.AddEdge(3, 2, 7);g.AddEdge(3, 4, 7);
- g.AddEdge(4, 2, 4);g.AddEdge(4, 5, 8);
-
- g.FordFulkerson(0, 5); // 指定source为0，target为5
- return 0;
- }
