例 5(9) 网络N 增量网络N(f) N(f)的分层网络 辅助网络AN(∫) 四、 Dinic算法1970) 基本思想:从任一可行流∫开始,反复进行如下过程: (1)构造增量网络N(∫);(2)对N(∫)分层并构造辅助网络AN(∫);(3)求AN(中一条x-y路P; (4)沿xy路P增流得到更大的流,并去掉所有的饱和弧。若此时AN(f)中仍存在xy路,则再沿新的 x-y路增流,直到剩余网络中没有xy路为止。反复执行上述四步直到新流∫的增量网络N(∫不能分层 为止,此时N中不再有∫可增路,因而得到最大流 更详细地说, Dinic算法从网络N的任一可行流∫开始,构造增量网络N(f),对N(后)分层并 构造辅助网络AN(后)。在AN(f)中找一条xy路P,沿P增加流,得到可行流∫,并去掉增流所导 致的饱和弧。若此时AN(G)中仍有xy路,再沿新的xy路增加流,得到可行流f2,并去掉增流所导 致的饱和弧。反复执行这个过程,直到剩余网络中没有xy路为止。此时所得的流记为f。 然后对f继续上述过程。经有限次循环后,得一可行流f0,此时AN/8)中不再有任何xy路, 即N中不存在∫可增路,从而f便是最大流。 注:构造增量网络的目的:将求N中可增路问题化为求N(∫)中有向xy路; 寸N(∫)分层并作辅助网络的目的:简化N(f),求N(中最短有向xy路 2. Dinic算法步骤: Step.在网络N(,x,y,AC)中任取一个可行流f,令P=0.,q=0,f=f0 step1.构造增量网络N(P) Step2对增量网络N(JP)分层并构造辅助网络AN(f)。如果在分层时汇点y得不到标号(即不能分 层),则结束,当前的f就是N的最大流;否则,转Step3。 Step3.(找AN(f)中的xy路)在辅助网络AN(f)中执行如下步骤 30.将源点x标号为(-1,∞),令i=0,V=x 31.若v在AN()中没有出弧,转34;否则在AN()任取v的一条出弧(v,v,),转32 32.设v的标号为(k,),令5=min),可},(其中是AN(f)中弧()当前的容量),将v 标号为(5) 33.若V,=y,转Step4;否则令i=j,转3.1;例： 四、Dinic 算法(1970) 1. 基本思想：从任一可行流 f 开始，反复进行如下过程： (1) 构造增量网络 N f ( ) ；(2) 对 N f ( ) 分层并构造辅助网络 AN f ( ) ；(3) 求 AN f ( ) 中一条 x-y 路 P； (4) 沿 x-y 路 P 增流得到更大的流，并去掉所有的饱和弧。若此时 AN f ( ) 中仍存在 x-y 路，则再沿新的 x-y 路增流，直到剩余网络中没有 x-y 路为止。反复执行上述四步直到新流 f 的增量网络 N f ( ) 不能分层 为止，此时 N 中不再有 f 可增路，因而得到最大流。 更详细地说，Dinic 算法从网络 N 的任一可行流 0f 开始，构造增量网络 0 N f ( ) ，对 0 N f ( ) 分层并 构造辅助网络 0 AN f ( )。在 0 AN f ( )中找一条 x-y 路 P，沿 P 增加流，得到可行流 1 0f ，并去掉增流所导 致的饱和弧。若此时 0 AN f ( )中仍有 x-y 路，再沿新的 x-y 路增加流，得到可行流 2 0f ，并去掉增流所导 致的饱和弧。反复执行这个过程，直到剩余网络中没有 x-y 路为止。此时所得的流记为 0 1f 。 然后对 0 1f 继续上述过程。经有限次循环后，得一可行流 0 k f ，此时 AN( 0 k f )中不再有任何 x-y 路， 即 N 中不存在 0 k f 可增路，从而 0 k f 便是最大流。 注：构造增量网络的目的：将求 N 中可增路问题化为求 N f ( ) 中有向 x-y 路； 对 N f ( ) 分层并作辅助网络的目的：简化 N f ( ) ，求 N f ( ) 中最短有向 x-y 路。 2. Dinic 算法步骤： Step0. 在网络 NV x y AC (,,,, )中任取一个可行流 0f ，令 , , 0 0 0 q p pq ff = = = ; Step1. 构造增量网络 q p N f ( ) 。 Step2. 对增量网络 q p N f ( ) 分层并构造辅助网络 q p AN f ( ) 。如果在分层时汇点 y 得不到标号（即不能分 层），则结束，当前的 q p f 就是 N 的最大流；否则，转 Step3 。 Step3. (找 q p AN f ( ) 中的 x-y 路) 在辅助网络 q p AN f ( ) 中执行如下步骤： 3.0. 将源点 x 标号为( ,) −1 ∞ ，令 i: = 0， i v = x； 3.1. 若 i v 在 q p AN f ( ) 中没有出弧，转 3.4；否则在 q p AN f ( ) 任取 i v 的一条出弧(, ) i j v v ，转 3.2； 3.2. 设 i v 的标号为(, )i k δ ，令 min{ , } j i ij δ = δ c ，(其中 ij c 是 q p AN f ( ) 中弧(i, j)当前的容量)，将 j v 标号为(, )j i δ ； 3.3. 若 j v = y，转 Step4；否则令 i = j，转 3.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) v4 v1 v3 x y v2 网络 N 增量网络 N ( f ) v4 v1 v3 x y v2 v4 v1 v3 x y v2 N ( f )的分层网络 辅助网络 AN ( f )