1、15.082 和 6.855J,最小全局切割動畫,2,初始化,飽和結點1發(fā)出的弧.,更新剩余網絡,3,初始化,2,4,5,3,6,1,計算到結點2的距離,判定可進入弧,我們將再也不會從結點1推進或者推進到結點1內.,4,推進/重標號,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,5,推進/重標號,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,6,推進/重標號,2,4,5,6,1,選擇一活動結

2、點,1,從結點3 推進.,1,3,2,5,6,4,1,1,6,4,6,5,1,6,4,1,3,2,3,1,1,7,推進/重標號,2,4,5,6,1,選擇一活動結點,1,重標號結點 3. 規(guī)則: 沒有空層允許.,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,8,間隙,令 t 表示當前漏結點. 令 dmax 是除了源結點外的結點的最大距離標號. 空層是有值 k 且 d(t) k dmax 以至于沒有結點j 是 d(j) = k. 如果我們把d(3)增加到 7, 我們創(chuàng)建了一個間隙.在這種情況下, 我們把d(j) 增加到 dmax + 1.,9,推進/重標號,2,4

3、,5,6,1,重標號結點 3 ，因此沒有創(chuàng)建空層.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,3,2,3,1,1,10,切割層,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,在剩余網絡中，沒有從切割層的結點到下方結點的路徑.,11,切割-層 rule,總是選擇在最低切割-層下方的活動結點. 如果每個活動結點是在或高于切割層, 那么停止，得到最大預流/ 最小切割.,12,推進/重標號,0,5,4,3,2,1,2,4,5,6,1,在最小切割層之下選擇一活動結

4、點.,1,1,3,2,5,6,4,1,6,4,6,5,2,6,4,1,2,1,1,3,從結點 4 推進.,4,13,推進/重標號,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,14,推進/重標號,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,15,推進/重標號,0,5,4,3,2,1,2,4,5,6,1,在最小切割層之下選擇一活動結點

5、.,1,3,2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,重標號結點 5，如果它將不創(chuàng)建空層.,1,5,16,尋找首個切割結束,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,最大預流和最小切割已經被發(fā)現(xiàn).,1,令T 是能到達漏結點所有結點.,17,結束尋找第一個切割,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,18,開始第二個切割,0,5,4,3,2,1,2,4,5,6,1,在最低層選擇新的漏結點,1,3,

6、2,5,6,4,2,6,3,4,5,2,8,5,2,1,3,使 結點 2 成為源結點,1,飽和從 結點 2出來的弧.,2,19,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,20,推進/重標號,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，如果它沒有創(chuàng)建空層.,5,2,3,21,推進/重標號,0,5,4,3

7、,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,第二個切割已經發(fā)現(xiàn).,令T 是所有能到達漏結點的結點,22,推進/重標號,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,23,開始第三次切割,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發(fā)出的弧.,24,開始第3次切割,0,5,4,3,2,1,2,

8、4,5,6,1,層3 仍然是切割層,1,3,2,5,6,4,3,5,2,5,2,7,3,在切割層下，仍然沒有活動結點結點.,5,2,我們已經發(fā)現(xiàn)了第3 個切割,令 T 是所有能從漏結點到達的結點.,25,第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,26,開始第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 發(fā)出的弧,27,我們已經找到第4和第5切割,0,5,4,3,2,1,2,4,5,6,1,1,3,2,5,6,4,5,2,9,3,5,2,在網絡中僅有的弧是從源結點出來的弧