即首先给出一个初始流,这样的流是存在的,例如零流。如果存在关于它的可增广轨 那么调整该轨上每条弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广 轨,则用同样的方法使流的值增大,继续这个过程,直到网络中不存在关于新得到流的 可增广轨为止,则该流就是所求的最大流 这种方法分为以下两个过程 A.标号过程:通过标号过程寻找一条可增广轨。 B增流过程:沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 (A)标号过程 (i)给发点标号为(s,∞) (ⅱi)若顶点x已经标号,则对x的所有未标号的邻接顶点y按以下规则标号: ①若(x,y)∈A,且J<ln时,令6,=mmn{u-f,o} 则给顶点y标号为(x,D),若Jy=ly,则不给顶点y标号。 ②(y,x)∈A,且fm>0,令,=mmn{/m,o,},则给y标号为(x,o,),若 fx=0,则不给y标号。 (ⅲi)不断地重复步骤(ⅱ)直到收点t被标号,或不再有顶点可以标号为止。当t 被标号时,表明存在一条从s到t的可增广轨,则转向增流过程(B)。如若【点不能被 标号,且不存在其它可以标号的顶点时,表明不存在从s到t的可增广轨,算法结束, 此时所获得的流就是最大流。 (B)增流过程 (i)令=t (i)若l的标号为(v,,),则∫mn=∫m+;若l的标号为(v,o,),则 fm=f-5 (ⅲi)若u=s,把全部标号去掉,并回到标号过程(A)。否则,令=v,并回 到增流过程(ⅱ) 求网络N=(s,t,V,A,U/)中的最大流x的算法的程序设计具体步骤如下: 对每个节点j,其标号包括两部分信息 (pred(i), max io) 该节点在可能的增广路中的前一个节点pred(j),以及沿该可能的增广路到该节点为止 可以增广的最大流量maxf() STEP0置初始可行流x(如零流):对节点t标号,即令maxf()=任意正值(如 STEP1若maxf()>0,继续下一步;否则停止,已经得到最大流,结束。 STEP2取消所有节点j∈V的标号,即令maxf()=0 pred(j)=0;令LST={S},对节点S标号,即令maxf(s)=充分大的正值。 STEP3如果LIST≠Φ且maxf(t)=0,继续下一步;否则:(3a)如果t已经有 标号(即maxf(ω)>0),则找到了一条增广路,沿该增广路对流x进行增广(增广的 流量为maxf(t),增广路可以根据pred回溯方便地得到),转 STEPI。 (3b)如果t没有标号(即LIST=Φ且maxf(t)=0),转 STEPI-64- 即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨， 那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广 轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的 可增广轨为止，则该流就是所求的最大流。 这种方法分为以下两个过程： A.标号过程：通过标号过程寻找一条可增广轨。 B.增流过程：沿着可增广轨增加网络的流量。 这两个过程的步骤分述如下。 （A）标号过程： （i）给发点标号为 ( ,) + s 。 （ii）若顶点 x 已经标号，则对 x 的所有未标号的邻接顶点 y 按以下规则标号： ① 若 (x, y)  A ，且 xy uxy f  时，令 min{ , } y xy xy x  = u − f  ， 则给顶点 y 标号为 ( , ) y x  + ，若 xy uxy f = ，则不给顶点 y 标号。 ② ( y, x)  A ，且 f yx  0 ，令 min{ , } y yx x  = f  ，则给 y 标号为 ( , ) y x  − ，若 f yx = 0 ，则不给 y 标号。 （iii）不断地重复步骤（ii）直到收点 t 被标号，或不再有顶点可以标号为止。当 t 被标号时，表明存在一条从 s 到 t 的可增广轨，则转向增流过程（B）。如若 t 点不能被 标号，且不存在其它可以标号的顶点时，表明不存在从 s 到 t 的可增广轨，算法结束， 此时所获得的流就是最大流。 （B）增流过程 （i）令 u = t 。 （ii）若 u 的标号为 t (v , + ），则 vu vu t f = f + ；若 u 的标号为 ( , ) t v  − ，则 uv uv t f = f − 。 （iii）若 u = s ，把全部标号去掉，并回到标号过程（A）。否则，令 u = v ，并回 到增流过程（ii）。 求网络 N = (s,t,V, A,U) 中的最大流 x 的算法的程序设计具体步骤如下： 对每个节点 j ，其标号包括两部分信息 (pred( j),max f(j)) 该节点在可能的增广路中的前一个节点 pred( j) ，以及沿该可能的增广路到该节点为止 可以增广的最大流量 max f( j)。 STEP0 置初始可行流 x （如零流）；对节点 t 标号，即令 max f(t) =任意正值（如 1）。 STEP1 若 max f( j)  0 ，继续下一步；否则停止，已经得到最大流，结束。 STEP2 取消所有节点 j V 的标号，即令 max f( j) = 0 ， pred( j) = 0 ；令 LIST={ s }，对节点 s 标号，即令 max f(s) = 充分大的正值。 STEP3 如果 LIST   且 max f(t) = 0 ，继续下一步；否则：（3a）如果 t 已经有 标号（即 max f(t)  0 ），则找到了一条增广路，沿该增广路对流 x 进行增广（增广的 流量为 max f(t) ，增广路可以根据 pred 回溯方便地得到），转 STEP1。 （3b）如果 t 没有标号（即 LIST=  且 max f(t) = 0 ），转 STEP1