Edmonds-Karp算法

Edmonds-Karp算法是<一个href="//www.parkandroid.com/wiki/ford-fulkerson-algorithm/" class="wiki_link" title="Ford-Fulkerson算法" target="_blank">Ford-Fulkerson算法．和Ford-Fulkerson一样，Edmonds-Karp也是一种处理<一个href="//www.parkandroid.com/wiki/max-flow-min-cut-algorithm/" class="wiki_link" title="最大流min-cut问题" target="_blank">最大流min-cut问题．

Ford-Fulkerson有时被称为方法，因为它的协议的某些部分没有指定。另一方面，Edmonds-Karp提供了完整的规范。最重要的是，它明确了这一点<一个href="//www.parkandroid.com/wiki/breadth-first-search/" class="wiki_link" title="广度优先搜索" target="_blank">广度优先搜索应该用于在程序的中间阶段寻找最短路径。

Edmonds-Karp改进了Ford-Fulkerson的运行时间<年代pan class="katex"> $E O \大(| | \ cdot f ^{*} \大)$ $O （ ∣ E ∣ \cdot f^{*} ）$ ,<年代pan class="katex"> $V O \大(| | \ cdot | E | ^ 2 \大)$ $O （ ∣ V ∣ \cdot ∣ E ∣^{2} ）$ ．这种改进很重要，因为它使Edmonds-Karp算法的运行时间独立于网络的最大流量，<年代pan class="katex"> $f ^ {*}$ $f^{*}$ ．

概述

寻找网络的最大流量首先用<一个href="//www.parkandroid.com/wiki/ford-fulkerson-algorithm/" class="wiki_link" title="Ford-Fulkerson算法" target="_blank">Ford-Fulkerson算法．网络通常被抽象地定义为一个图，<年代pan class="katex"> $G$ $G$ ，它有一组顶点，<年代pan class="katex"> $V$ $V$ 由一组边连接，<年代pan class="katex"> $E$ $E$ ．有一个来源，<年代pan class="katex"> $年代$ $年代$ ，还有一个水槽，<年代pan class="katex"> $t$ $t$ ，它们代表着流体从哪里来，流向哪里。求解通过网络的最大流量<一个href="//www.parkandroid.com/wiki/max-flow-min-cut-algorithm/" class="wiki_link" title="最大流min-cut定理" target="_blank">最大流min-cut定理之后，该算法被用于创建Ford-Fulkerson算法。

Edmonds-Karp和<一个href="//www.parkandroid.com/wiki/ford-fulkerson-algorithm/" class="wiki_link" title="Ford-Fulkerson" target="_blank">Ford-Fulkerson除了一个非常重要的特点。明确了增广路径的搜索顺序。回顾一下Ford-Fulkerson wiki，在寻找网络的最大流量时，扩展路径和残差图是需要理解的两个重要概念。

扩展路径就是从源到接收器的任何当前可以使用更多流的路径。在整个算法过程中，流量是单调增加的。因此，有时从源到汇的路径可以有更多的流量，这是一个增广路径。

残差图，记为<年代pan class="katex"> $G_f$ $G_{f}$ ，对于一个图，<年代pan class="katex"> $G$ $G$ ，共享相同的顶点集。不同的是边缘。在每一轮算法中，都会找到一条增广路径。找到这条路径后，新的残差图的边集会发生变化。沿着小路，每条边<年代pan class="katex"> $u, v$ $u ， v$ 会失去与增广路径中那条边对应的权值。每一个反向边<年代pan class="katex"> $u v,$ $v ， u$ 会增加体重。原始图中不在增广路径内的边不受影响。一旦残差图中没有从源到汇的路径，算法终止。

Edmonds-Karp与Ford-Fulkerson的不同之处在于它选择下一个增广路径时使用<一个href="//www.parkandroid.com/wiki/breadth-first-search-bfs/" class="wiki_link" title="广度优先搜索(bfs)" target="_blank">广度优先搜索(bfs)．所以，如果有多条增广路径可供选择，Edmonds-Karp一定会选择最短的从源到汇的增广路径。

算法伪代码

下面是Edmonds-Karp的一个基本的、非语言特定的伪代码示例:

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

输入C [n * n]:能力矩阵E [n * n]:邻接矩阵s:来源t:水槽输出f:最大流量Edmonds-Karp: f = 0 / /流最初0 f = [n * n] / /剩余容量数组而真实:m P =广度优先搜索(C、E s、t、f)如果m = 0:打破f = f + m v = t v ! = s: u = P [v] [u, v] = f (u, v) - m / /这是减少剩余容量的增广路径(v, u) = f (v, u) + m / /这是增加的剩余容量反向边v = u返回f

在这段伪代码中，流初始值为零，初始剩余容量数组为全零。然后，外部循环执行，直到剩余图中没有更多从源到接收器的路径为止(这些循环的数量在<一个t一个rget="_blank" rel="nofollow" href="#complexity-proof">下面的部分）.

在这个循环中，我们正在执行<一个href="//www.parkandroid.com/wiki/breadth-first-search-bfs/" class="wiki_link" title="广度优先搜索" target="_blank">广度优先搜索寻找从源到有可用容量的接收器的最短路径。这种对BFS的微小改变非常容易，因为我们使用的是剩余容量矩阵F它基本上告诉我们在给定的边上是否有可用的容量。

一旦我们找到有剩余容量的路径，米我们把这个容量加到目前的最大流量上。然后，代码通过网络回溯，从接收器开始t．当它回溯时，它会找到当前顶点的父顶点，它被定义为u．然后，代码更新剩余流矩阵F反映新发现的增广路径容量米．v然后设置为父元素，并且重复内部循环，直到它到达源顶点。

复杂的证明

埃德蒙斯-卡普依赖于许多证明和<一个href="//www.parkandroid.com/wiki/big-o-notation/" class="wiki_link" title="复杂性" target="_blank">复杂性被描述为<一个href="//www.parkandroid.com/wiki/ford-fulkerson-algorithm/" class="wiki_link" title="Ford-Fulkerson" target="_blank">Ford-Fulkerson．来证明这个实现是可以运行的<年代pan class="katex"> $O (V \ cdot E ^ 2)$ $O （ V \cdot E^{2} ）$ ，必须证明两个陈述是正确的。首先，在算法的每一次迭代中，源和剩余图中所有其他顶点之间的最短路径必须增加<一个href="//www.parkandroid.com/wiki/monotonically/?wiki_title=monotonic" class="wiki_link new" title="单调" target="_blank" rel="nofollow">单调．也就是说，它是总是增加。第二，流量增加的总数是<年代pan class="katex"> $O (V \ cdot E)$ $O （ V \cdot E ）$ ．如果最短路径在残差图中总是增加的(因此在原图中是减少的)，并且存在最多<年代pan class="katex"> $V \ cdot E$ $V \cdot E$ 流的扩充，那么复杂性的边界将被很好地定义。

单调增加路径长度

为了证明残差图中所有顶点的最短路径总是递增的，可以考虑一个矛盾。因此，考虑一个流量增加导致最短路径减少。想象一下,<年代pan class="katex"> $f$ $f$ 是这样的流量之前的扩充，和那个<年代pan class="katex"> $急性{f} \$ $\overset{ˊ}{f}$ 是之后的流量。有一个顶点，<年代pan class="katex"> $v$ $v$ ,这样<年代pan class="katex"> $Distance_{\急性{f}}(s, v) \lt Distance_ {f}(s, v)$ $d 我年代 t 一个 n c e_{\overset{ˊ}{f}} （年代， v ） < d 我年代 t 一个 n c e_{f} （年代， v ）$ 因为反向流动比原始流动要小。再定义一个顶点，<年代pan class="katex"> $u$ $u$ ，这样就有了一条从<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $v$ $v$ 通过<年代pan class="katex"> $u$ $u$ 这是最短路径<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $v$ $v$ 在<年代pan class="katex"> $G_f$ $G_{f}$ ．也就是说最短路径是从<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $v$ $v$ 1是否大于最短路径<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $u$ $u$ 为简单起见,所以

$距离{\急性{f}} (s, u) =距离{\急性{f}} (s, v) - 1。$

最短路径是从<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $u$ $u$ 没有随着新的流量而减少吗<年代pan class="katex"> $急性{f} \$ $\overset{ˊ}{f}$ 因为我们的选择<年代pan class="katex"> $v$ $v$ ,所以

$距离{\急性{f}}(年代,u) \组的距离{f} (s, u)。$

然而,边缘<年代pan class="katex"> $(u, v)$ $（ u ， v ）$ 不能在残差图中，<年代pan class="katex"> $G_f$ $G_{f}$ ．如果是，则会有以下关系(注意我们使用的是整数边长):

$\begin{aligned} distance_f(s, v) &\leq distance_f(s, u) + 1 &&\qquad (\textrm{由三角形不相等})\\ distance_f(s, v) &\leq distance_{\急性{f} (s, u) + 1 &&\qquad \big(\textrm{因为最短路径随}\急性{f}\大而减少)\\ distance_f(s, v) &\leq distance_{\急性{f} (s, v). &&\qquad \大(\textrm{因为(s, u)和(s, v)}\大(\textrm{因为(s, u)和(s, v)}\大(\textrm{因为(s, u)和(s, v)}\大(\textrm{因为(s, u)和(s, v)}\大)\ end{aligned}$

最后一个等式违背了这个关系式

$Distance_{\急性{f}}(s, v) \lt distance_f(s, v)。$

换句话说，最短路径实际上并没有随着流量的增加而减少<年代pan class="katex"> $急性{f} \$ $\overset{ˊ}{f}$ ．这个矛盾证明告诉我们，在残差图中，最短路径是单调增加的，它将Edmonds-Karp迭代一次的长度限定为<年代pan class="katex"> $O (E)$ $O （ E ）$ ．

的迭代次数

下一个证明涉及到Edmonds-Karp为了找到网络的最大流量必须经过的迭代次数。我们的目标是证明确实存在<年代pan class="katex"> $O (V \ cdot E)$ $O （ V \cdot E ）$ Edmonds-Karp迭代。

一条边被定义为<年代trong>至关重要的在增广路径上，当且仅当边缘的剩余容量等于路径的剩余容量。换句话说，临界边的容量会被这个增广路径填满。一旦我们增强了这条路径，有问题的边缘将从残差网络中消失。我们必须证明每一个<年代pan class="katex"> $| E |$ $∣ E ∣$ 边最多可以成为关键<年代pan class="katex"> $V \压裂{| |}{2}$ $\frac{∣ V ∣}{2}$ 次了。

让<年代pan class="katex"> $u$ $u$ 而且<年代pan class="katex"> $v$ $v$ 是图中由一条边连接的顶点，让<年代pan class="katex"> $年代$ $年代$ 是源。当这条边是第一个临界时，距离关系将是

$Distance_f (s, v) = Distance_f (s, u) + 1。$

一旦这种流动增加，正如我们已经看到的，边缘<年代pan class="katex"> $(u, v)$ $（ u ， v ）$ 会从残网中消失。这条边不能重新出现，除非流从<年代pan class="katex"> $u$ $u$ 来<年代pan class="katex"> $v$ $v$ 是减少的，只有当边<年代pan class="katex"> $(u, v)$ $（ v ， u ）$ 出现在增广路径上。如果<年代pan class="katex"> $急性{f} \$ $\overset{ˊ}{f}$ 当这发生的时候是流吗

$距离{\急性{f}} (s, u) =距离{\急性{f}} (s, v) + 1。$

回顾本节的第一个证明<年代pan class="katex"> $Distance_f (s, v) \leq distance_{\急性{f}}(s, v)$ $d 我年代 t 一个 n c e_{f} （年代， v ） \leq d 我年代 t 一个 n c e_{\overset{ˊ}{f}} （年代， v ）$ ,我们有

$\{对齐}开始距离{\急性{f}} (s, u) & =距离{\急性{f}} (s, v) + 1 \ \距离{\急性{f}} (s, u) & \组的距离{f} (s, v) + 1 \ \距离{\急性{f}} (s, u) & \组的距离{f} (s, u) + 2。结束\{对齐}$

最后一个等式非常重要。它是说在这段时间之间<年代pan class="katex"> $(u, v)$ $（ u ， v ）$ 第一次成为关键<年代pan class="katex"> $（$ $（$ 当流<年代pan class="katex"> $f),$ $f ），$ 到下一次变得至关重要的时候<年代pan class="katex"> $（$ $（$ 当流<年代pan class="katex"> $急性{\ f})$ $\overset{ˊ}{f} ），$ 源和之间的距离<年代pan class="katex"> $u$ $u$ 增加了至少2.

最短路径上的中间顶点<年代pan class="katex"> $年代$ $年代$ 来<年代pan class="katex"> $u$ $u$ 不能包含<年代pan class="katex"> $年代$ $年代$ ，<年代pan class="katex"> $u$ $u$ ,或<年代pan class="katex"> $t$ $t$ 到顶点的距离<年代pan class="katex"> $u$ $u$ 最多是<年代pan class="katex"> $| | - 2$ $∣ V ∣ - 2$ ．这个分数的分母是2，因为每当一条边变得临界时，到源的距离至少增加2。所以,<年代pan class="katex"> $(u, v)$ $（ u ， v ）$ 最多能成为关键<年代pan class="katex"> $V \压裂{| | - 2}{2}$ $\frac{∣ V ∣ - 2}{2}$ 次数，一共<年代pan class="katex"> $V O \大(| | \大)$ $O （ ∣ V ∣ ）$ 次了。

因为有<年代pan class="katex"> $E O \大(| | \大)$ $O （ ∣ E ∣ ）$ 总顶点对可以，为边<年代pan class="katex"> $(u, v)$ $（ u ， v ）$ ,成为关键<年代pan class="katex"> $V O \大(| | \大)$ $O （ ∣ V ∣ ）$ 乘以，Edmonds-Karp迭代的总次数是<年代pan class="katex"> $V O \大(| | \ cdot | E | \大)。$ $O （ ∣ V ∣ \cdot ∣ E ∣ ）．$

复杂性

Edmonds-Karp对<一个href="//www.parkandroid.com/wiki/ford-fulkerson-algorithm/" class="wiki_link" title="Ford-Fulkerson算法" target="_blank">Ford-Fulkerson算法．Ford-Fulkerson简单地指出，在每次迭代中，流至少增加1。每次迭代需要<年代pan class="katex"> $E O \大(| | \大)$ $O （ ∣ E ∣ ）$ 时间。当我们看到<一个t一个rget="_blank" rel="nofollow" href="#complexity-proof">以上．Ford-Fulkerson所能保证的是最大流量是在<年代pan class="katex"> $E O \大(| | \ cdot f ^{*} \大)$ $O （ ∣ E ∣ \cdot f^{*} ）$ ,在那里<年代pan class="katex"> $f ^ {*}$ $f^{*}$ 是最大流量本身。

Edmonds-Karp去除了对复杂性的最大流的依赖，使得它更适合具有较大最大流的图，比如下面这个:

最大流量大但边和顶点少的图

通过显示Edmonds-Karp运行每个迭代<年代pan class="katex"> $E O \大(| | \大)$ $O （ ∣ E ∣ ）$ 时间和那最多也就有<年代pan class="katex"> $V | | \ cdot | |$ $∣ V ∣ \cdot ∣ E ∣$ 迭代，Edmonds-Karp的边界是<年代pan class="katex"> $V O \大(| | \ cdot | E ^ 2 | \大)$ $O （ ∣ V ∣ \cdot ∣ E^{2} ∣ ）$ ．

Python实现示例

下面是Edmonds-Karp的Python实现:

12 34 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

进口小数defEdmondsKarp（E，C，年代，t)：n＝len（C）流＝0F＝[[0为y在范围（n）]为x在范围（n）]而真正的：P＝［-1为x在范围（n）]P［年代］＝-2米＝［0为x在范围（n）]米［年代］＝小数．小数（“无穷”）BFSq＝［］BFSq．附加（年代）pathFlow，P＝BFSEK（E，C，年代，t，F，P，米，BFSq）如果pathFlow= =0：打破流＝流+pathFlowv＝t而v! =年代：u＝P［v］F［u] [v］＝F［u] [v］+pathFlowF［v] [u］＝F［v] [u］-pathFlowv＝u返回流defBFSEK（E，C，年代，t，F，P，米，BFSq)：而（len（BFSq）>0)：u＝BFSq．流行（0）为v在E［u]：如果C［u] [v］-F［u] [v］>0而且P［v］= =-1：P［v］＝u米［v］＝最小值（米［u),C［u] [v］-F［u] [v])如果v! =t：BFSq．附加（v）其他的：返回米［t),P返回0，P

它紧跟伪代码。唯一的大变化是由于Python，广度优先搜索被抽象到它自己的函数中<一个href="//www.parkandroid.com/wiki/variables-and-scope/" class="wiki_link" title="范围" target="_blank">范围的原因。

如果我们从<一个t一个rget="_blank" rel="nofollow" href="#complexity">复杂的部分，我们可以用这个代码来求解它的最大流量。首先，我们需要定义输入，即邻接矩阵E，容量矩阵C,源年代，和水槽t．

1 2 3 4

> > > E =[[1,2],[2、3],[3 ], []] >>> C = [[0, 1000000, 1000000, 0], [0, 0, 1, 1000000], [0, 0, 0, 1000000], [0, 0, 0, 0]] > > > s = 0 > > > t = 3

这里所发生的就是我们给图中的4个顶点编号。源是0,A是1,B是2，接收器是3。在邻接矩阵中[1,2]是<年代pan class="katex"> $0 ^ \文本{th}$ $0^{th}$ 列表的索引意味着有一条从0到1和从0到2的边。在容量矩阵中C，事实是[0, 1000000, 1000000, 0]是在<年代pan class="katex"> $0 ^ \文本{th}$ $0^{th}$ Index表示从0到0和从0到3之间有0个容量，从0到1和从0到2之间有1000000个容量。记住Python使用0索引!

现在我们可以运行代码了。

1 2	`EdmondsKarp(E, C, s, t) 2000000`

正如预期的那样，从源到汇的最大流量是2000000。

有关……

内容