容量調(diào)整算法

1、15.082 和 6.855J容量調(diào)整算法初始的代價(jià)和結(jié)點(diǎn)的勢(shì)123544122567000002初始的容量和供應(yīng)/需求1235410202025252030235-2-7-193設(shè)置 = 16. 這開始 -調(diào)整階段1235410202025252030235-2-7-19我們從超額 的結(jié)點(diǎn)發(fā)送流到虧損 的結(jié)點(diǎn).我們忽略容量 的結(jié)點(diǎn). 4選擇供應(yīng)結(jié)點(diǎn)且尋找最短路徑12354412256770688最短路徑距離最短路徑樹標(biāo)記為粗體和藍(lán)色.5更新結(jié)點(diǎn)的勢(shì)和即約代價(jià)1235441225670-7-8-8-60000631為了更新結(jié)點(diǎn)的勢(shì)，減去最短路徑距離.6沿著在G(x,16)中的最短路徑發(fā)送流12

2、3541從結(jié)點(diǎn)1發(fā)送流到結(jié)點(diǎn)5.202025252030235-2-7-19應(yīng)該發(fā)送多少流？107更新剩余網(wǎng)絡(luò)123541從結(jié)點(diǎn)1發(fā)送19 單位的流到結(jié)點(diǎn) 5.2020625130235-2-7010-19 419198這就結(jié)束了 16-調(diào)整 階段. 123541當(dāng)對(duì)某i有e(i) 時(shí)，繼續(xù) -調(diào)整階段. 對(duì)某些j有e(j) -時(shí). 存在從 i 到 j的路徑.20206251305-2-7010 419199這個(gè)開始和結(jié)束 8-調(diào)整階段123541當(dāng)對(duì)某i有e(i) 時(shí)，繼續(xù) -調(diào)整階段. 對(duì)某些j有e(j) -時(shí). 存在從 i 到 j的路徑.20206251305-2-7010 419191

3、0這個(gè)開始和結(jié)束 4-調(diào)整階段. 12354120206251305-2-7010 41919如果存在容量至少是 4 和負(fù)即約代價(jià)的弧，我們?cè)趺崔k？11選擇一 “大的超額” 結(jié)點(diǎn)和尋找最短路徑12354110-7-8-8-60006300最短路徑樹是標(biāo)記為粗體和藍(lán)色的.012更新結(jié)點(diǎn)勢(shì)和即約代價(jià)12354100-7-8-8-60402001-11-12-10-4為了更新結(jié)點(diǎn)勢(shì),減去最短路徑距離.說(shuō)明: 低容量的弧可以有負(fù)即約代價(jià).13沿在G(x,4)中的最短路徑發(fā)送流.12354120206251305-2-7010 41919從結(jié)點(diǎn)1發(fā)送流到結(jié)點(diǎn)7應(yīng)該發(fā)送多少流？14更新剩余網(wǎng)絡(luò)123541

4、162010251265-2-306 41915從結(jié)點(diǎn)1發(fā)送4 單位的流到結(jié)點(diǎn)3 0-744415這結(jié)束 4-調(diào)整階段.123541162010251265-2-3061915沒(méi)有結(jié)點(diǎn) j 有 e(j) -4. 044416開始 2-調(diào)整階段123541162010251265-2-3061915沒(méi)有結(jié)點(diǎn)j 有e(j) -4. 0444如果存在容量至少是 4 和負(fù)即約代價(jià)的弧，我們?cè)趺崔k？17沿著最短路徑發(fā)送流123541162010251265-2-3061915 0444從結(jié)點(diǎn)2發(fā)送流到結(jié)點(diǎn)4.應(yīng)該發(fā)送多少？18更新剩余網(wǎng)絡(luò)123541162010251265-2-3041915 0464

5、從結(jié)點(diǎn) 2 發(fā)送2個(gè)單位的流到結(jié)點(diǎn)43019沿著最短路徑發(fā)送流12354116201025126-3041915 0464從結(jié)點(diǎn)2發(fā)送流到結(jié)點(diǎn)330發(fā)送了多少流？20更新剩余網(wǎng)絡(luò)12354113201325126-3011912 0794從結(jié)點(diǎn) 2 到結(jié)點(diǎn)3 發(fā)送了3 單位的流300021這結(jié)束了2-調(diào)整階段. 12354113201325126011912 0794我們是最優(yōu)的嗎？00022開始 1-調(diào)整階段.12354113201325126011912 0794飽和任何容量至少是1且有負(fù)代價(jià)的弧.000即約代價(jià)是負(fù)的23更新剩余網(wǎng)絡(luò)1235411320132526012012 -1794從結(jié)點(diǎn)3發(fā)送流到結(jié)點(diǎn)1.010注釋: 結(jié)點(diǎn)1現(xiàn)在是有虧損的結(jié)點(diǎn).24更新剩余網(wǎng)絡(luò)12354114201225270220130683從結(jié)點(diǎn)3發(fā)送1單位的流到結(jié)點(diǎn)3.000這個(gè)流是最優(yōu)的嗎？25最終最優(yōu)的流1235410,82