发布时间 : 星期二 文章信息与计算科学毕业论文最大流问题及应用更新完毕开始阅读
山东科技大学本科毕业设计（论文）
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