福特-富尔克森算法

发表于 更新于 分类于 Waline：

这个算法是图论中比较经典的最大流问题的算法，使用场景有很多，比如在互联网中已知中间链路每一段的最大流量，如何最快速地把数据从一个节点传递到另一个节点。

算法核心思路

假设上图为一个网络拓扑图，连接节点之间的边表示各种通道，上面的数字代表通道流量的上限，即通道的容量。每一条边的实际流量不可以超过通道的容量。

假定我们现在要从数据中心S，最快速地将数据传递到T，需要制定一个方案，使得从S到T的流量可以达到最大。

从图中可以看出，一些边由于自身容量很小，可能会成为瓶颈，而要想实现网络流量最大化，就要在一些节点进行分流，比如从A到D的边流量最大是8，显然消化不了从S到A的20，因此需要从A到B分流。

要解决这个问题，我们需要这样思考。将一个连通图从中间一刀劈开，分为G1和G2两部分，起始节点和目标节点分别在G1和G2，那么显然整个网络能够传输的最大流量不会超过连接G1和G2这两部分所有边的容量之和。

比如，我们把起始节点S放在G1，其他部分放在G2，如图中左边弧形切割线所示。从S出发的最大流显然无法超过被切割的三条边，也就是SA，SB，SC的总和。类似的，我们也可以把目标节点放在G2，其他放在G1，就是图中右边弧线的切割方式，网络中能够传输到T的总流量一定也不会超过DT，ET，FT三条边容量的总和。

我们可以任意划分节点，只要S和T在图的两部分就可以，计算出每一种划分方式连接G1和G2所有边的总和，然后其中最小的值就是整个图的容量瓶颈。

接下来的问题是，是否有一种设定各条边上流量的方式，让从S到T的流量能够等于最小切割流量。答案是肯定的。我们观察上图，L2对应的切割就是整个图的瓶颈，要想整个图的流量达到最大，瓶颈处的流量就必须饱和。如果被L2切割的边中有一条边的流量没有达到容量，那么说明整个网络还有进一步增加的可能性，我们就需要想办法调整每一条边的流量，让L2的各条边流量都达到饱和。

调整流量的本质就是找到一条从S到T流量尚未饱和的路径，然后增加这条路径上的每一条边的流量（当然减少某条边上的反向流量也等同于增加这条边的流量）。这条流量可以增加的路径，被称为增广路径。可以证明，只要从S到T的流量还没有达到最小切割流量，就可以不断找到增广路径，直到流量达到这个值为止。

算法伪代码

对于一个有权重的图G（V，E），如果（u,v）属于E，那么它的权重为capacity(u,v)，表示这条边的容量。我们用另一个数组flow(u,v),表示每条边已经分配的流量。此外我们使用一个临时数组remaining(u,v)表示每条边还剩余的可分配的流量。

由remaining这个数组和节点的集合构成一个剩余流量图G_r，如果u，v之间没有剩余流量了，那么(u,v)这条边就不存在于剩余流量图G_r中

1
2
3
4
5
6
7
8
9
10
11
12
13
Ford-Fulkerson(G, start, end) {
    while(G_r中存在从start到end的一条路径path) {
        remaining(path) = min{remaining(u,v), (u,v)在路径path上};
        for each (u, v) in path {
            // 如果这条边已经被分配了流量，增加其流量，否则减少其反方向流量
            if (flow(u,v) > 0) {
                flow(u,v) += remaining(path)
            } else {
                flow(v,u) -= remaining(path)
            }
        }
    }
}

上述伪代码中有一点在于如何从剩余流量图G_r中找到从start到end的一条路径path，答案是BFS。

所以如果假设最大容量是F，那么这个算法的时间复杂度是O(|E|*F)，即最差的情况是每次找到增广路径，都只让流量增加1，每次找增广路径都要遍历所有的边

算法具体实现

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/ Ford - Fulkerson algorith in C

#include <stdio.h>

#define A 0
#define B 1
#define C 2
#define MAX_NODES 1000
#define O 1000000000

int n;
int e;
int capacity[MAX_NODES][MAX_NODES];
int flow[MAX_NODES][MAX_NODES];
int color[MAX_NODES];
int pred[MAX_NODES];

int min(int x, int y) {
  return x < y ? x : y;
}

int head, tail;
int q[MAX_NODES + 2];

void enqueue(int x) {
  q[tail] = x;
  tail++;
  color[x] = B;
}

int dequeue() {
  int x = q[head];
  head++;
  color[x] = C;
  return x;
}

// Using BFS as a searching algorithm
int bfs(int start, int target) {
  int u, v;
  for (u = 0; u < n; u++) {
    color[u] = A;
  }
  head = tail = 0;
  enqueue(start);
  pred[start] = -1;
  while (head != tail) {
    u = dequeue();
    for (v = 0; v < n; v++) {
      if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {
        enqueue(v);
        pred[v] = u;
      }
    }
  }
  return color[target] == C;
}

// Applying fordfulkerson algorithm
int fordFulkerson(int source, int sink) {
  int i, j, u;
  int max_flow = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      flow[i][j] = 0;
    }
  }

  // Updating the residual values of edges
  while (bfs(source, sink)) {
    int increment = O;
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      increment = min(increment, capacity[pred[u]][u] - flow[pred[u]][u]);
    }
    for (u = n - 1; pred[u] >= 0; u = pred[u]) {
      flow[pred[u]][u] += increment;
      flow[u][pred[u]] -= increment;
    }
    // Adding the path flows
    max_flow += increment;
  }
  return max_flow;
}

int main() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      capacity[i][j] = 0;
    }
  }
  n = 6;
  e = 7;

  capacity[0][1] = 8;
  capacity[0][4] = 3;
  capacity[1][2] = 9;
  capacity[2][4] = 7;
  capacity[2][5] = 2;
  capacity[3][5] = 5;
  capacity[4][2] = 7;
  capacity[4][3] = 4;

  int s = 0, t = 5;
  printf("Max Flow: %d\n", fordFulkerson(s, t));
}

扩展

二分图配对问题

其实在讲第一部分的时候，不知道大家有没有想起这个二分图的配对问题，两个问题都涉及了寻找增广路径

从上图可以看出，要实现L两边节点的最大配对，其实就等同于实现S到T的最大流，有两对节点能够配对，流量就是2，有三对能过够配对，流量就是3，所以这个问题可以用福特-富尔克森算法来解，这个算法对于边的最大容量和最小容量之比很大的图效率都不高，但是在二分图中，边的最大和最小容量都是1，所以这种算法的复杂度只有O(|E|)。

当然，二分图有更简单的方法，因为它每一部分内部的点之间没有边，所以可以采用寻找交替路径的方法，也就是匈牙利算法