当检查完u的所有邻点之后,u称为已标已查顶点。 反复进行上述标、查过程,最终必出现两种结果之 ()汇点y获得标号,此时已得到∫可增路。沿该路增流。 (i)y点未获得标号,但已没有已标未查顶点(所有已标顶点都已被查,没有更多的新标号顶点) 此时当前的流∫即为最大流[设当前已标已查的顶点之集为S,则(S,S)为最小割 例如:网络M(V,x,y,A,O及其上一个流f,(括号内数字是弧容量)。 35(9) v15(9) 0(5) 0(2)k6为y2c 2379)v2 情况():获得一条∫可增路 情况(i):已得到最大流和最小割 求网络最大流的Ford- Fulkerson标号算法 输入:网络N(V,x,y,A,C) 输出:网络N中一个最大流。 第0步(初始化):对a∈A,令∫(a)=0 第1步:给源点x标号(x,∞)。L:={x},S=Φ。其中L表示已标未査集,S表示已标已查集 第2步:任取l∈L,检查u的每个尚未标号的邻点v (1)若v∈N'(u),w尚未标号且C(u,yv)>f(u,v),则给v标号(u,+,l(v),其中 l(v)=min{(au),C(l,y)-f(l,v)}。令L:=LU{v}。 (2)若v∈N(a),ν尚未标号且f(v,u)>0,则给ν标号(u,-,l(v),其中 l(v)=min{(au),f(v,u)}。令L:=LU{v}。 第3步:重复第2步,直到汇点y被标号,或y未被标号但L=Φ为止。 若是后者,算法结束,当前流是最大流 若是前者,转下步。 2 第5步:若〓的标号为(w,+,l(=),则令f(W,=)=f(,)+l(y) 若的标号为(V,-,l(二=),则令∫(=,w)=f(二,w)-l(y) 注:不论二是哪个点,此处总是l(y),因1⑦)是最大的可增量(沿可增路)。 第6步:若W≠x,则令x=w,转第5步; 否则,去掉所有的顶点标号,转第1步当检查完 u 的所有邻点之后，u 称为已标已查顶点。 反复进行上述标、查过程，最终必出现两种结果之一： (i) 汇点 y 获得标号，此时已得到 f 可增路。沿该路增流。 (ii) y 点未获得标号，但已没有已标未查顶点(所有已标顶点都已被查，没有更多的新标号顶点)。 此时当前的流 f 即为最大流[设当前已标已查的顶点之集为 S，则(, ) S S 为最小割] 例如：网络 N(V, x, y, A, C)及其上一个流 f,（括号内数字是弧容量）。 情况(i)：获得一条 f 可增路 情况(ii)：已得到最大流和最小割 求网络最大流的 Ford－Fulkerson 标号算法： 输入：网络 NV x y AC (,,,, ) 输出：网络 N 中一个最大流。 第 0 步(初始化)：对∀ ∈a A ，令 f a() 0 = ； 第 1 步：给源点 x 标号(, ) x ∞ 。 L xS : { }, = =Φ 。其中 L 表示已标未查集，S 表示已标已查集。 第 2 步：任取u L ∈ ，检查 u 的每个尚未标号的邻点 v。 (1) 若 vNu( ) + ∈ ， v 尚未标号且 Cuv f uv (,) (,) > ，则给 v 标 号 ( , , ( )) u lv + ，其中 lv lu Cuv f uv ( ) min{ ( ), ( , ) ( , )} = − 。令 LLv : {} = ∪ 。 (2) 若 vNu( ) − ∈ ， v 尚未标号且 f vu (, ) 0 > ，则给 v 标 号 ( , , ( )) u lv − ，其中 lv lu f vu ( ) min{ ( ), ( , )} = 。令 LLv : {} = ∪ 。 第 3 步：重复第 2 步，直到汇点 y 被标号，或 y 未被标号但 L = Φ 为止。 若是后者，算法结束，当前流是最大流； 若是前者，转下步。 第 4 步：令 z y = 。 第 5 步：若 z 的标号为( , , ( )) w lz + ，则令 f (,) (,) () wz f wz ly = + ； 若 z 的标号为( , , ( )) w lz − ，则令 f (, ) (, ) ( ) zw f zw ly = − 。 注：不论 z 是哪个点，此处总是 l (y)，因 l (y)是最大的可增量 (沿可增路)。 第 6 步：若 w x ≠ ，则令 z w = ，转第 5 步； 否则，去掉所有的顶点标号，转第 1 步。 v4 v1 v3 x y v2 7(7) 7(9) 5(8) 0(5) 5(9) 0(2) 0(6) 7(10) 5(5) 2 2 3 3 3 ∞ v4 v1 v3 x y v2 7(7) 9(9) 7(8) 2(5) 5(9) 0(2) 0(6) 9(10) 5(5) 1 1 1 ∞