资源描述
Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,15.082,和,6.855J,初始化,1,3,2,5,6,4,1,1,1,5,3,4,6,饱和结点,1,发出的弧,.,更新剩余网络,2,初始化,0,5,4,3,2,1,2,4,5,3,6,1,计算到结点,2,的距离,判定可进入弧,1,1,3,2,5,6,4,1,1,1,5,3,4,6,5,1,6,4,1,3,我们将再也不会从结点,1,推进或者推进到结点,1,内,.,3,推进,/,重标号,0,5,4,3,2,1,2,4,5,3,6,1,选择一活动结点,1,Carry out,推进,/,重标号,1,3,2,5,6,4,1,1,3,4,6,5,1,6,4,1,3,3,2,4,推进,/,重标号,0,5,4,3,2,1,2,4,5,3,6,1,选择一活动结点,1,重标号,.,不存在可进入弧,.,1,3,2,5,6,4,1,1,6,4,6,5,1,6,4,1,3,2,3,3,5,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,选择一活动结点,1,从结点,3,推进,.,1,3,2,5,6,4,1,1,6,4,6,5,1,6,4,1,3,2,3,1,1,6,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,选择一活动结点,1,重标号结点,3.,规则,:,没有空层允许,.,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,7,间隙,令,t,表示当前漏结点,.,令,d,max,是除了源结点外的结点的最大距离标号,.,空层,是有值,k,且,d(t),k,d,max,以至于没有结点,j,是,d(j) = k.,如果我们把,d(3),增加到,7,我们创建了一个间隙,.,在这种情况下,我们把,d(j),增加到,d,max,+ 1.,8,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,重标号结点,3,，因此没有,创建,空层,.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,3,3,9,切割层,0,5,4,3,2,1,2,4,5,6,1,切割层,是仅有一个结点需要重标号的,层,.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,2,1,1,3,在剩余网络中，没有从切割层的结点到下方结点的路径,.,10,切割,-,层,rule,总是选择在最低切割,-,层下方的活动结点,.,如果每个活动结点是在或高于切割层,那么停止，得到最大预流,/,最小切割,.,11,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下,选择一活动结点,.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,2,1,1,3,从结点,4,推进,.,4,12,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点,.,1,3,2,5,6,4,1,6,3,6,5,2,6,5,1,2,1,3,从结点,6,推进,.,2,6,13,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点,.,1,3,2,5,6,4,1,6,3,4,5,2,8,5,1,2,1,3,从结点,5,推进,.,2,5,14,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,在最小切割层之下选择一活动结点,.,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,重标号结点,5,，如果它将不创建空层,.,1,5,15,寻找首个切割结束,0,5,4,3,2,1,2,4,5,6,1,在最低切割层下,不存在活动结点,.,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,最大预流和最小切割已经被发现,.,1,令,T,是,能到达漏结点,所有结点,.,16,结束寻找第一个切割,0,5,4,3,2,1,2,4,5,6,1,这是第一个最小切割,.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,17,开始第二个切割,0,5,4,3,2,1,2,4,5,6,1,在最低层选择新的漏结点,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,使 结点,2,成为源结点,1,饱和从,结点,2,出来的弧,.,2,5,5,18,Beginning of the second,切割,0,5,4,3,2,1,2,4,5,6,1,我们将不再从结点,2,推进或 推进到结点,2.,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,没有必要物理上合并结点,1,和,2.,5,2,19,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,选择一活动结点,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,重标号结点,3,，如果它没有创建空层,.,5,2,3,20,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,层,4,变成了一切割层,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,在切割层下，没有活动结点,.,5,2,第二个切割已经发现,.,令,T,是所有能到达漏结点的结点,21,推进,/,重标号,0,5,4,3,2,1,2,4,5,6,1,这是第二次切割,.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,22,开始第三次切割,0,5,4,3,2,1,2,4,5,6,1,让结点,5,是源结点,1,3,2,5,6,4,3,4,5,2,8,5,2,7,3,结点,6,变成新的漏结点,5,2,饱和从结点,5,发出的弧,.,5,5,6,6,23,开始第,3,次切割,0,5,4,3,2,1,2,4,5,6,1,层,3,仍然是切割层,1,3,2,5,6,4,3,5,2,5,2,7,3,在切割层下，仍然没有活动结点结点,.,5,2,我们已经发现了第,3,个切割,令,T,是所有能从漏结点到达的结点,.,24,第,3,切割,0,5,4,3,2,1,2,4,5,6,1,上面的切割是最好的切割，,1, 2, 5,在一边，结点,6,在另一边,.,3,1,3,2,5,6,4,1,1,1,5,3,4,6,25,开始第,4,个切割,0,5,4,3,2,1,2,4,5,6,1,结点,6,变成一源结点,1,3,2,5,6,4,3,5,2,5,2,7,3,结点,4,变成下一个源结点,5,2,饱和从结点,6,发出的弧,6,6,4,4,26,这是切割,4,和,5,1,3,2,5,6,4,1,1,1,5,3,4,6,1,3,2,5,6,4,1,1,1,5,3,4,6,切割,4,切割,5,27,全局最小切割是切割数,2,0,5,4,3,2,1,2,4,5,6,1,3,1,3,2,5,6,4,1,1,1,5,3,4,6,算法结束时，结点,1,在源边，得到最小切割,.,28,
展开阅读全文