山东科技大学本科毕业设计（论文）

找—条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献[2]）。

采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献[6]）。

Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献[18]）。现在我们考虑只有一个发点vs和一个收点vt的容量网络，应用Ford-Fulkerson标号算法求解它的最大流

3.1.2 Ford-Fulkerson标号法的具体步骤 A:标号过程

步骤0 确定一初始可行流{fij}，可以是零流。 步骤1 给发点vs以标号[?,vs]。

步骤2 选择一个已标号但未检查的点vi，并作如下检查：

① 对每一弧(vi,vj)，若vj未给标号，而且cij?fij时，即流出未饱和弧,给vj以标号[?j,vi]；

② 对每一弧(vj,vi)，若vj未给标号，而且fji?0时，即流入非零流弧，给vj以标号[?j,?vi]；

??cij?fij其中：?j?min{?i,?},?????fji10

若(vi,vj)为流出未饱和弧若(vj,vi)为流入非零流弧

山东科技大学本科毕业设计（论文）

步骤3 重复步骤2直到收点vt被标号，或不再有顶点可以标号为止。 如果点给了标号说明存在一条增广路径，故转向增广过程B。如若点vt不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。 B：增广过程

由终点vt开始，使用标号的第二个元素构造一条增广路径?(点vt的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在?上作调整得新的可行流

{fij}，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令?为vt标号的第一个元素的值，作

?fij??(vi,vj)是?上前向弧??fij??fij??(vj,vi)是?上后向弧???fij其它

以新的可行流{fij}代替原来的可行流，去掉所有标号，转标号过程的步骤1。

采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献[14]）。

11

山东科技大学本科毕业设计（论文）

3.2 Edmonds-Karp修正算法

Ford-Fulkerson标号算法理论上存在着严重的弱点，以下图3.2.1为例各边上的权是它们的容量，其最大流流量为2m，若增广路径选择得不好,即交替地采用sabeft和sdebct作为增广路径，则每次增广只能使总的流量增加1,当初始流选为零流，无疑需作2m?1次的增加流量才能使之达到最大，可见Ford-Fulkerson算法的时间复杂度不仅依赖于网络的规模(即依赖于网络点数和边数)，还和各边的容量有关,而容量可以是任意的正整数。如图3.2.1中，当sabeft和sdebct交替作为增广路径时，be弧交替地以前向弧和后向弧出现。利用Ford-Fulkerson算法求解就很麻烦了（参见文献[8]）。

对于Ford-Fulkerson算法,由于增广路径选取的任意性造成了该算法不是好算法，Edmonds和Karp对Ford-Fulkerson算法作修正，可概括为一句话：“先给标号的先扫描”。它的意思是对已给标号的顶点v进行扫描时，先对所有和v邻接的未给标号的顶点给予标号。具体的说图3.2.1的例子，顶点s先标记，所以应该先扫描，因此避免了Ford-Fulkerson算法那样交替地出现sabeft,sdebct的情况，也就避免了be弧交替地以前向弧和后向弧来回摇摆的局面。所以Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从s流向t的（参见文献[3]）。

s m m d 12 a m m b m c m 1 m e 图3.2.1 m f t 山东科技大学本科毕业设计（论文）

现在我们仍考虑只有一个发点vs和一个收点vt的网络图，Edmonds-Karp修正算法的主要步骤是： ① 确定一初始可行流{fij}，其流量W(f)。

② 检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整

(检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。 ③ 将当前的可行流调整成一个流量更大的新可行流，再由②检验。

同样地，我们通常用观察法确定网络的—个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点vs起，逐步寻找vs至各点vi间的增广路径，若能找到vs至vi的一条增广路径，则给点vi标号[?i,?i]（其中第一个标号?i即为vs至vi这条增广路径上的最大可调整量，第二个标号?i则表示这条可行流上点vi的前一点是?i点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点vt标上号，表示已找到一条由vs至vt的增广路径。反之，如果标号过程进行至某一步中止了，而vt尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下：

① 给发点vs标号[?,vs]，含义为vs至vs的增广路径已找到，前一点为vs，这条增广路径上的调整量为?。选与vs关联的从vs流出的未饱和弧

13

山东科技大学本科毕业设计（论文）

(vs,vi)或流入vs的非零流弧(vi,vs)，给vi标号[?i,vs] (对于流出弧)或

[?i,?vs] (对于流入弧)。

??csi?fsi若(vs,vi)为流出未饱和弧其中：?i??

??fsi若(vi,vs)为流入非零弧② 将顶点集分为互补的二个点集S、S，其中S为已标号点集，S为未标号点集；

③ 考虑所有这样的弧(vi,vj)或(vj,vi)，其中vi?S,vj?S。若弧(vi,vj)为从vi流出的未饱和弧，则给vj标号[?j,vi]。其中?j?min{?i,cij?fij}；若弧(vj,vi)为流入vi的非零流弧，则给vj标号[?j,?vi]。其中

?j?min{?i,fij}。依此进行，得到的结果是：

(a)S??，说明网络中存在增广路径?，则由标号点反向追踪找出?，转第④步；

(b)S??，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(S,S)。

?fij????④ 调整过程：取??min{?j}，令fij??fij??vj?????fij(vi,vj)是?上前向弧(vj,vi)是?上后向弧 其它得到新可行流{fij}，流量W(f)?W(f)??，即比原可行流流量增加了?，再转①步。

用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。

14