1、15.082 和 6.855J,容量調(diào)整算法,2,初始的代價(jià)和結(jié)點(diǎn)的勢(shì),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é)點(diǎn)發(fā)送流到虧損 的結(jié)點(diǎn).,我們忽略容量 的結(jié)點(diǎn).,5,選擇供應(yīng)結(jié)點(diǎn)且尋找最短路徑,1,2,3,5,4,4,1,2,2,5,6,7,7,0,6,8,8,最短路徑距離,最短路徑樹標(biāo)記為粗體和藍(lán)色

2、.,6,更新結(jié)點(diǎn)的勢(shì)和即約代價(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é)點(diǎn)的勢(shì)，減去最短路徑距離.,7,沿著在G(x,16)中的最短路徑發(fā)送流,1,2,3,5,4,1,從結(jié)點(diǎn)1發(fā)送流到結(jié)點(diǎn)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é)點(diǎn)1發(fā)送19 單位的流到結(jié)點(diǎn) 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)對(duì)某i有e

3、(i) 時(shí)，繼續(xù) -調(diào)整階段. 對(duì)某些j有e(j) -時(shí). 存在從 i 到 j的路徑.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,10,這個(gè)開始和結(jié)束 8-調(diào)整階段,1,2,3,5,4,1,當(dāng)對(duì)某i有e(i) 時(shí)，繼續(xù) -調(diào)整階段. 對(duì)某些j有e(j) -時(shí). 存在從 i 到 j的路徑.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,11,這個(gè)開始和結(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 和負(fù)即約代價(jià)的弧，我們?cè)趺崔k？,12,選擇一

4、 “大的超額” 結(jié)點(diǎn)和尋找最短路徑,1,2,3,5,4,1,1,0,-7,-8,-8,-6,0,0,0,6,3,0,0,最短路徑樹是標(biāo)記為粗體和藍(lán)色的.,0,13,更新結(jié)點(diǎn)勢(shì)和即約代價(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é)點(diǎn)勢(shì),減去最短路徑距離.,說(shuō)明: 低容量的弧可以有負(fù)即約代價(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é)點(diǎn)1發(fā)送流到結(jié)點(diǎn)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é)點(diǎn)1發(fā)送4 單位的流到結(jié)點(diǎn)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,沒(méi)有結(jié)點(diǎn) 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,沒(méi)有結(jié)點(diǎn)j 有e(j) -4.,0,4,4,4,如果存在容量至少是 4 和負(fù)即約代價(jià)的弧，我們?cè)趺崔k？,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é)點(diǎn)2發(fā)送流到結(jié)點(diǎn)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é)點(diǎn) 2 發(fā)送2個(gè)單位的流到結(jié)點(diǎn)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é)點(diǎn)2發(fā)送流到結(jié)點(diǎn)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é)點(diǎn) 2 到結(jié)點(diǎn)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且有負(fù)代價(jià)的弧.,0,0,0,即約代價(jià)是負(fù)的,24,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,13,20,13,25,26,0,1,20,12,-1,7,9,4,從結(jié)點(diǎn)3發(fā)送流到結(jié)點(diǎn)1.,0,1,0,注釋: 結(jié)點(diǎn)1現(xiàn)在是有虧損的結(jié)點(diǎn).,25,更新剩余網(wǎng)絡(luò),1,2,3,5,4,1,14,20,12,25,27,0,2,20,13,0,6,8,3,從結(jié)點(diǎn)3發(fā)送1單位的流到結(jié)點(diǎn)3.,0,0,0,這個(gè)流是最優(yōu)的嗎？,26,最終最優(yōu)的流,1,2,3,5,4,10,8,