圖論動畫-容量調(diào)整算法.ppt

1、15.082 和 6.855J,容量調(diào)整算法,2,初始的代價和結(jié)點的勢,1,2,3,5,4,4,1,2,2,5,6,7,0,0,0,0,0,3,初始的容量和供應(yīng)/需求,1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,4,設(shè)置 = 16. 這開始 -調(diào)整階段,1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,我們從超額 的結(jié)點發(fā)送流到虧損 的結(jié)點.,我們忽略容量 的結(jié)點.,5,選擇供應(yīng)結(jié)點且尋找最短路徑,1,2,3,5,4,4,1,2,2,5,6,7,7,0,6,8,8,最短路徑距離,最短路徑樹標(biāo)記為粗體和藍色

2、.,6,更新結(jié)點的勢和即約代價,1,2,3,5,4,4,1,2,2,5,6,7,0,-7,-8,-8,-6,0,0,0,0,6,3,1,為了更新結(jié)點的勢，減去最短路徑距離.,7,沿著在G(x,16)中的最短路徑發(fā)送流,1,2,3,5,4,1,從結(jié)點1發(fā)送流到結(jié)點5.,20,20,25,25,20,30,23,5,-2,-7,-19,應(yīng)該發(fā)送多少流？,10,8,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,從結(jié)點1發(fā)送19 單位的流到結(jié)點 5.,20,20,6,25,1,30,23,5,-2,-7,0,10,-19,4,19,19,9,這就結(jié)束了 16-調(diào)整 階段.,1,2,3,5,4,1,當(dāng)對某i有e

3、(i) 時，繼續(xù) -調(diào)整階段. 對某些j有e(j) -時. 存在從 i 到 j的路徑.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,10,這個開始和結(jié)束 8-調(diào)整階段,1,2,3,5,4,1,當(dāng)對某i有e(i) 時，繼續(xù) -調(diào)整階段. 對某些j有e(j) -時. 存在從 i 到 j的路徑.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,11,這個開始和結(jié)束 4-調(diào)整階段.,1,2,3,5,4,1,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,如果存在容量至少是 4 和負即約代價的弧，我們怎么辦？,12,選擇一

4、 “大的超額” 結(jié)點和尋找最短路徑,1,2,3,5,4,1,1,0,-7,-8,-8,-6,0,0,0,6,3,0,0,最短路徑樹是標(biāo)記為粗體和藍色的.,0,13,更新結(jié)點勢和即約代價,1,2,3,5,4,1,0,0,-7,-8,-8,-6,0,4,0,2,0,0,1,-11,-12,-10,-4,為了更新結(jié)點勢,減去最短路徑距離.,說明: 低容量的弧可以有負即約代價.,14,沿在G(x,4)中的最短路徑發(fā)送流.,1,2,3,5,4,1,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,從結(jié)點1發(fā)送流到結(jié)點7,應(yīng)該發(fā)送多少流？,15,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1

5、,16,20,10,25,1,26,5,-2,-3,0,6,4,19,15,從結(jié)點1發(fā)送4 單位的流到結(jié)點3,0,-7,4,4,4,16,這結(jié)束 4-調(diào)整階段.,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,19,15,沒有結(jié)點 j 有 e(j) -4.,0,4,4,4,17,開始 2-調(diào)整階段,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,19,15,沒有結(jié)點j 有e(j) -4.,0,4,4,4,如果存在容量至少是 4 和負即約代價的弧，我們怎么辦？,18,沿著最短路徑發(fā)送流,1,2,3,5,4,1,16,20,10,

6、25,1,26,5,-2,-3,0,6,19,15,0,4,4,4,從結(jié)點2發(fā)送流到結(jié)點4.,應(yīng)該發(fā)送多少？,19,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,4,19,15,0,4,6,4,從結(jié)點 2 發(fā)送2個單位的流到結(jié)點4,3,0,20,沿著最短路徑發(fā)送流,1,2,3,5,4,1,16,20,10,25,1,26,-3,0,4,19,15,0,4,6,4,從結(jié)點2發(fā)送流到結(jié)點3,3,0,發(fā)送了多少流？,21,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,13,20,13,25,1,26,-3,0,1,19,12,0,7,9,4,從結(jié)點 2 到結(jié)點3

7、 發(fā)送了3 單位的流,3,0,0,0,22,這結(jié)束了2-調(diào)整階段.,1,2,3,5,4,1,13,20,13,25,1,26,0,1,19,12,0,7,9,4,我們是最優(yōu)的嗎？,0,0,0,23,開始 1-調(diào)整階段.,1,2,3,5,4,1,13,20,13,25,1,26,0,1,19,12,0,7,9,4,飽和任何容量至少是1且有負代價的弧.,0,0,0,即約代價是負的,24,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,13,20,13,25,26,0,1,20,12,-1,7,9,4,從結(jié)點3發(fā)送流到結(jié)點1.,0,1,0,注釋: 結(jié)點1現(xiàn)在是有虧損的結(jié)點.,25,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,14,20,12,25,27,0,2,20,13,0,6,8,3,從結(jié)點3發(fā)送1單位的流到結(jié)點3.,0,0,0,這個流是最優(yōu)的嗎？,26,最終最優(yōu)的流,1,2,3,5,4,10,8,