Ford-Fulkerson算法

Ford-Fulkerson算法是一种解决最大流min-cut问题。也就是说，给定一个具有一定权重的顶点和顶点之间的边的网络，网络一次能处理多少“流”?流可以指任何东西，但通常它指的是通过计算机网络的数据。

它是1956年由福特和福克森发现的。这种算法有时被称为方法，因为它的协议的部分没有完全指定，并且在不同的实现中可能有所不同。算法通常是指解决问题的特定协议，而方法是解决问题的更一般的方法。

Ford-Fulkerson算法假设输入是a图， $G$，加上一个源顶点， $年代$和一个下沉顶点， $t$．图是加权图的任何表示形式，其中顶点由指定权重的边连接。还必须有一个源顶点和汇聚顶点来理解流网络的开始和结束。

Ford-Fulkerson的复杂性 $E O \大(| | \ cdot f ^{*} \大),$在哪里 $f ^ {*}$是网络的最大流量。Ford-Fulkerson算法最终由Edmonds-Karp算法，它在 $O \大(V ^ 2 \ cdot E \大)$时间，与最大流量值无关。

算法背后的直觉非常简单(尽管实现细节可能会掩盖这一点)。想象一个由汽车组成的交通网络。每条路可以容纳一定数量的汽车。这可以用下面的图表来说明。

流网络

直觉是这样的:只要有一条从源到汇的路径可以在整个过程中消耗一些流量，我们就发送它。这条路径叫做增广路径．我们一直这样做直到没有更多的增广路径。在上图中，我们可以从沿最顶端路径发送2辆车开始(因为只有2辆车可以通过最后一段)。然后我们可以让3辆车沿着底部路径行驶总共是5辆车。最后，我们可以沿顶部路径发送2辆车，将它们发送到底部路径，并通过水槽。现在发送的车辆总数是7辆，这是最大流量。

为什么在上一个例子的最后一个增广路径中只能发送2辆车?

显示答案

我们已经让两辆车沿着上面的路径进入了第一条增广路径。这意味着沿着上面路径的前两条边已经在 $2/4$能力。所以这些边最多只能容纳2辆车，所以它们是最后增广路径的限制因素。

这就是为什么对于更大更复杂的流网络，扩展路径的计算非常棘手。来处理这件事,剩余图在发现并最大化每个增广路径后生成。残差图显示了不同路径的容量与其当前流量之间的差异，可以精确计算出未来的增广路径。 $_ \广场$

这个方法的伪代码相当短;但是，还有一些功能需要进一步讨论。下面是简单的伪代码。

这个伪代码不是用任何特定的计算机语言编写的。相反，它是对算法的非正式的、高级的描述。

Ford-Fulkerson算法 $($图 $G$、源 $年代$,沉 $t):$

1 2 3 4 5 6 7

现在这是有目的的歧义G_f = createResidualGraph() path = findAugmentingPath(G_f, s, t)返回流

基本上，这个简化版本说的是，只要有一条从源到汇的路径可以处理更多的流，就发送该流。下面是伪代码的一个版本，它更深入地解释了流增强:

12 3 4 5 6 7 8 9 10 11 12

为每个边缘流= 0 (u, v)在G:流(u, v) = 0虽然是一个路径,p, s - > t的残余网络G_f: residual_capacity (p) = min (residual_capacity (u, v): p) (u, v)的流=流+ residual_capacity (p)对每条边(u, v) p:如果(u, v)是一个向前边:流(u, v) =流(u, v) + residual_capacity (p):流(u, v) =流(u, v) - residual_capacity (p)回流

这种算法定义更明确。唯一模棱两可的一点是第8行上的“前沿”术语。当残差图， $G_f$，则可以创建与原始图相比方向相反的边。如果一条边存在于原始图中，那么它就是“向前的边”， $G$．如果它是原始边的反转，它被称为“向后边”。

残差图是计算最大流量的重要中间步骤。正如在伪代码，每一步都计算它们，这样就可以找到从源到汇的增广路径。要了解这些是如何创建和使用的，我们可以使用来自直觉部分。

然而，在查看残差图之前，理解一个重要的属性非常重要。剩余容量是上述伪代码中使用的一个术语，它在残差图创建中起着重要的作用。剩余容量被定义为给定流量被取走后的新容量。换句话说，对于给定的边 $(u, v)$，剩余容量， $c_f$被定义为

$C_f (u, v) = c(u, v) - f(u, v)。$

但是，还必须有一个剩余的容量反向边缘。的最大流min-cut定理在网络中必须保留流的状态。因此，以下等式始终成立:

$F (u, v) = -f(v, u)$

有了这些工具，就有可能计算出流网络中任何边(向前或向后)的剩余容量。然后，这些剩余容量被用来构成一个剩余网络， $G_f$．

使用原始的直觉网络并在顶点上添加标签，我们现在有了这个:

Ford-Fulkerson之前的流网络

结果表明，最初可沿最顶部路径推动2单位流量。当这种情况发生时，只有三条边受到影响:(S, A)、(A, B)和(B, T)。(S, A)和(A, B)受到同样的影响，因为它们具有相同的容量。会发生两件事情:

1. 在前进的方向上，现在边缘的剩余容量等于 $C_f (u, v) = c(u, v) - f(u, v)$．流量等于2，所以(S, A)和(A, B)的剩余容量降为2，而边(B, T)的剩余容量为0。
2. 向后的方向，现在边缘的剩余容量等于 $C_f (v, u) = c(v, u) - f(v, u)$．由于流保存，这可以写成 $C_f (v, u) = c(v, u) + f(u, v)$．由于这些后向边的容量最初是0，所有后向边(T, B) (B, A)和(A, S)现在的剩余容量是2。

当用这些新边构造一个新的残差图时，任何残差容量为0 (B, T)的边都不包括在内。

1轮后的残差图

现在，必须找到一条新的增广路径 $($最上面的路径永远不能再次使用，因为边(B, T)被擦除了 $）.$底部路径可以选择，可以沿着它发送3个流。结果如下图所示:

2轮后的残差图

最后，可以沿路径[(S, a)， (a, B)， (B, C)， (C, D)， (D, T)]发送一个2的流，因为沿该路径的最小剩余容量是2。完成后的最终残差图如下:

3轮后的残差图

从源到接收器没有更多的路径，所以不能有更多的增广路径。因此，循环是完整的。流量7是最大流量。

Ford-Fulkerson算法很容易实现，一旦概念剩余图是理解。正如在本wiki的介绍中所提到的，这种算法通常被称为方法，因为在残差图中寻找增广路径的方法没有完全指定。此实现是实现此目的的一种方法。

下面的实现没有经过实战测试，只是作为一个学习工具．

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

类顶点：def__init__(自我，的名字，源＝假，水槽＝假)：自我．的名字＝的名字自我．源＝源自我．水槽＝水槽类边缘：def__init__(自我，开始，结束，能力)：自我．开始＝开始自我．结束＝结束自我．能力＝能力自我．流＝0自我．returnEdge＝没有一个类FlowNetwork：def__init__(自我)：自我．顶点＝［］自我．网络＝{}defgetSource(自我)：为顶点在自我．顶点：如果顶点．源= =真正的：返回顶点返回没有一个defgetSink(自我)：为顶点在自我．顶点：如果顶点．水槽= =真正的：返回顶点返回没有一个defgetVertex(自我，的名字)：为顶点在自我．顶点：如果的名字= =顶点．的名字：返回顶点defvertexInNetwork(自我，的名字)：为顶点在自我．顶点：如果顶点．的名字= =的名字：返回真正的返回假defgetEdges(自我)：allEdges＝［］为顶点在自我．网络：为边缘在自我．网络［顶点]：allEdges．附加(边缘）返回allEdgesdefaddVertex(自我，的名字，源＝假，水槽＝假)：如果源= =真正的而且水槽= =真正的：返回"顶点不能是源和汇"如果自我．vertexInNetwork(的名字)：返回“重复的顶点”如果源= =真正的：如果自我．getSource（）! =没有一个：返回“源”已经存在如果水槽= =真正的：如果自我．getSink（）! =没有一个：返回“沉已经存在”newVertex＝顶点(的名字，源，水槽）自我．顶点．附加(newVertex）自我．网络［newVertex．的名字］＝［］defaddEdge(自我，开始，结束，能力)：如果开始= =结束：返回“不能有相同的开始和结束”如果自我．vertexInNetwork(开始）= =假：返回"起始顶点尚未添加"如果自我．vertexInNetwork(结束）= =假：返回"还没有添加结束顶点"newEdge＝边缘(开始，结束，能力）returnEdge＝边缘(结束，开始，0）newEdge．returnEdge＝returnEdgereturnEdge．returnEdge＝newEdge顶点＝自我．getVertex(开始）自我．网络［顶点．的名字］．附加(newEdge）returnVertex＝自我．getVertex(结束）自我．网络［returnVertex．的名字］．附加(returnEdge）defgetPath(自我，开始，结束，路径)：如果开始= =结束：返回路径为边缘在自我．网络［开始]：residualCapacity＝边缘．能力-边缘．流如果residualCapacity>0而且不(边缘，residualCapacity）在路径：结果＝自我．getPath(边缘．结束，结束，路径+((边缘，residualCapacity)))如果结果! =没有一个：返回结果defcalculateMaxFlow(自我)：源＝自我．getSource（）水槽＝自我．getSink（）如果源= =没有一个或水槽= =没有一个：返回“网络无源无汇”路径＝自我．getPath(源．的名字，水槽．的名字，[])而路径! =没有一个：流＝最小值(边缘［1］为边缘在路径）为边缘，res在路径：边缘．流+ =流边缘．returnEdge．流- =流路径＝自我．getPath(源．的名字，水槽．的名字，[])返回总和(边缘．流为边缘在自我．网络［源．的名字]）

在线定义的类1是一个简单的顶点类。它只有一个名称，我们用它来创建边缘(和调试)，不管顶点是源还是汇。在网上7,边缘类是定义。这个类有一个起始顶点(只是顶点的名称，而不是类实例)、一个结束顶点、一个容量、一个流和一个指向残差图中使用的返回边的指针。边的容量是它的总权重可以而边的流量就是它的重量目前携带。

的FlowNetwork在线定义的类15有两个属性。的顶点属性是图中顶点的所有实例的列表。这个列表保存了整个对象，将顶点的名称链接到它的源属性和汇聚属性。的网络字典是一种数据结构，它将每个顶点的名称映射到对应顶点的所有边。通过简单地让顶点的名称充当字典键，我们可以轻松地在“顶点”和“网络”之间来回切换，以适应算法的需要。

行20-48包含各种帮助函数，使后面的函数更容易，并有助于减少代码重复。例如，在线函数32，getVertex ()取一个顶点名，然后找到整个顶点对象FlowNetwork的顶点属性。

addVertex ()在网上50在检查各种错误情况以确保可以添加顶点后，向图中添加顶点。它将整个顶点添加到顶点在一行62并将顶点名称添加到在线的空边列表中63．addEdge ()在网上65首先检查开始顶点和结束顶点是否都在图中，并且它们不是同一个顶点。然后，它创建新的边和相应的返回边，其容量为0。然后将新边在线添加到网络映射中77并将返回边添加到在线上的同一地图79．

'getPath()'函数在网上81做这门课的重要工作。这是一个递归函数它从给定顶点开始遍历流网络，并计算每条边的剩余容量。此剩余容量用于决定下一个函数中沿给定路径发送多少流量。该路径不断增长，直到到达流网络的末端;在这一点上，递归的基本情况被在线调用82函数结束。

calculateMaxFlow ()在网上91是什么电话getPath用正确的参数和加起来的最大流量。它首先找到网络的源和汇。然后，在线计算初始增广路径96．然后，我们开始使用重要的Ford-Fulkerson方法，并在仍然存在路径的情况下继续计算流量。当存在路径时，在路径的每个边缘都有一个增加的容量，因此可以在线计算流量98．该流被添加到正向边缘，并从反向边缘中减去。然后，计算另一个路径并恢复该过程。最后，我们只需要计算从源头流出的总流量，因为这是通过整个网络的确切流量(因为我们只有一个源头)。

为了说明以上Python实现，我们可以构造完全相同的图从直觉部分。

1 2 3 4 5 6 7 8 9 10 11

fn＝FlowNetwork（）fn．addVertex(“年代”，真正的，假）fn．addVertex(“t”，假，真正的）地图(fn．addVertex，［“一个”，“b”，“c”，' d ']）fn．addEdge(“年代”，“一个”，4）fn．addEdge(“一个”，“b”，4）fn．addEdge(“b”，“t”，2）fn．addEdge(“年代”，“c”，3.）fn．addEdge(“c”，' d '，6）fn．addEdge(' d '，“t”，6）fn．addEdge(“b”，“c”，3.）

流动网络被创建了，所以它顶点而且网络可以检查。但是，这些属性包含完整的对象顶点属性包含顶点对象和网络属性包含边缘对象。所以我们需要清理一下。

1 2 3 4

>>>［顶点．的名字为顶点在fn．顶点］［“年代”，“t”，“一个”，“b”，“c”，' d '］>>>［＇% s->% s＇％(e．开始，e．结束）为e在fn．getEdges())［“- >”，“a - b >”，c - >年代”，“c - > d '，“c - > b”，“b - >“，“b - > t”，“b - > c”，“d - > c”，“d - > t”，“s - >“，“s - > c”，“t - > b”，“t - > d '］

记住这些边getEdges ()也包含所有的反边。现在，这个类可以计算它自己的最大流量。

1 2

>>>fn．calculateMaxFlow（）7

这和我们之前检查发现的答案是一样的。

当'fn.calculateMaxFlow()'被调用时，'getEdges()'中边缘的'capacity'和'flow'属性会发生什么?

提示:对于前向边和后向边的答案略有不同。

显示答案

一旦这个过程完成，所有向前的边都被尽可能地填满，而反向的边反映了被填满的状态。随着最大流min-cut定理状态下，网络的总流量必须被保留。对于一条有端点的边 $(u, v)$，向前和向后边的流和将为0，就像过程开始时一样。

这是通话前后的差别fn.calculateMaxFlow ()：

1 2 3 4 5 6

>>>［＇% s->% s；% s/% s＇％(e．开始，e．结束，e．流，e．能力）为e在fn．getEdges())［a - >年代;-4/0的，“- > b;4/4拍的，c - >年代;-3/0的，“c - > d;5/6的，“c - > b;-2/0的，“b - >;-4/0的，“b - > t;2/2的，“b - c >;2/3的，' d - > c;-5/0的，' d - > t;5/6的，' s - >;4/4拍的，' s - > c;3/3”，“t - > b;-2/0的，的t - > d;-5/0的］>>>fn．calculateMaxFlow（）7>>>［＇% s->% s；% s/% s＇％(e．开始，e．结束，e．流，e．能力）为e在fn．getEdges())［a - >年代;-4/0的，“- > b;4/4拍的，c - >年代;-3/0的，“c - > d;5/6的，“c - > b;-2/0的，“b - >;-4/0的，“b - > t;2/2的，“b - c >;2/3的，' d - > c;-5/0的，' d - > t;5/6的，' s - >;4/4拍的，' s - > c;3/3”，“t - > b;-2/0的，的t - > d;-5/0的］

如果你画出所有的边，你会看到你所创建的图形是相同的剩余图部分。

Ford-Fulkerson的分析很大程度上取决于如何找到增广路径。典型的方法是使用广度优先搜索找到路径。如果使用这种方法，Ford-Fulkerson运行时间为多项式。

如果所有流都是整数，则最多运行Ford-Fulkerson的while循环 $| f ^ {*} |$次, $f ^ {*}$是最大流量。这是因为流在每次迭代中最多增加1。

在while循环中查找增广路径需要 $O \大(V + E ^{} \大),$在哪里 $E ^ {'}$是残差图中的边的集合。这可以简化为 $O (E)$．Ford-Fulkerson的运行时间是 $大(E O \ \ cdot | f ^{*} | \大)。$