圖論動畫-連續(xù)最短路徑算法

1、115.082J 和和 6.855J連續(xù)最短路徑算法連續(xù)最短路徑算法2初始代價和結(jié)點勢初始代價和結(jié)點勢123544122567000003初始容量和供應(yīng)初始容量和供應(yīng)/需求需求1235410202025252030235-2-7-194選擇供應(yīng)結(jié)點和發(fā)現(xiàn)最短路徑選擇供應(yīng)結(jié)點和發(fā)現(xiàn)最短路徑12354412256770688最短路徑距離最短路徑樹最短路徑樹標(biāo)記為標(biāo)記為粗體粗體和藍色和藍色5更新結(jié)點勢和即約代價更新結(jié)點勢和即約代價1235441225670-7-8-8-60000636沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點點 (沿著有即約代價勢沿著有即約代價勢 0

2、 的弧的弧)1235410202025252030235-2-7-19從結(jié)點從結(jié)點1發(fā)發(fā)送送7單位的單位的流到結(jié)點流到結(jié)點3弧數(shù)是剩余容弧數(shù)是剩余容量量.紅色的弧有即紅色的弧有即約代價約代價 07更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)1235410202025251330235-2-7-19弧弧(3,1) 有即有即約代價約代價07160如果一條弧添如果一條弧添加到加到 G(x), 那么那么它有即約代價它有即約代價 0且是紅色的且是紅色的.在剩余網(wǎng)絡(luò)中的在剩余網(wǎng)絡(luò)中的弧將總有非負即弧將總有非負即約代價約代價.8注釋注釋這點上，你應(yīng)該選擇源結(jié)點，然后找到從源結(jié)點到其他這點上，你應(yīng)該選擇源結(jié)點，然后找到從源結(jié)點到

3、其他結(jié)點的最短路徑，然后更新剩余網(wǎng)絡(luò)結(jié)點的最短路徑，然后更新剩余網(wǎng)絡(luò).然而，在剩余網(wǎng)絡(luò)中仍然有然而，在剩余網(wǎng)絡(luò)中仍然有0即約代價的路徑即約代價的路徑,且使用它且使用它們是有意義的們是有意義的. 這種啟發(fā)式方法在實踐中非常有用這種啟發(fā)式方法在實踐中非常有用.9沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點點12354102020252513305-2-19從結(jié)點從結(jié)點1發(fā)送發(fā)送2個單位的流到個單位的流到結(jié)點結(jié)點4.7160回憶，紅色的弧回憶，紅色的弧有即約代價是有即約代價是0.10更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)12354102018252511305-2-19在在1-3-4

4、上，從結(jié)上，從結(jié)點點1發(fā)送發(fā)送2單位的單位的流到結(jié)點流到結(jié)點 4.9160214011沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點點12354102018252511305-19從結(jié)點從結(jié)點1發(fā)送流到發(fā)送流到結(jié)點結(jié)點5.902140應(yīng)該發(fā)送多應(yīng)該發(fā)送多少流？少流？12更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)123541020181425305-19從結(jié)點從結(jié)點1到結(jié)點到結(jié)點5發(fā)發(fā)送送11 單位的流單位的流.2002140113-813選擇供應(yīng)結(jié)點以及選擇最短路徑選擇供應(yīng)結(jié)點以及選擇最短路徑1235410-7-8-8-600006300最短路徑樹標(biāo)記最短路徑樹標(biāo)記為為粗體和藍色粗體

5、和藍色.在結(jié)點上的值是在結(jié)點上的值是當(dāng)前結(jié)點勢當(dāng)前結(jié)點勢.14更新結(jié)點的勢和即約代價更新結(jié)點的勢和即約代價1235410-7-8-8-603003300-11-11-90為了得到新結(jié)點為了得到新結(jié)點的勢，從老的勢的勢，從老的勢中減去最短路徑中減去最短路徑距離距離.15沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點點123541020181425305從結(jié)點從結(jié)點1發(fā)送流到結(jié)發(fā)送流到結(jié)點點520020113-8發(fā)送多少流？發(fā)送多少流？16更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)123548202012252852000131-8223-6從結(jié)點從結(jié)點 1 發(fā)送發(fā)送2 單位的流到結(jié)點單

6、位的流到結(jié)點517選擇供應(yīng)結(jié)點且尋找最短路徑選擇供應(yīng)結(jié)點且尋找最短路徑1235410-7-11-11-9030030000最短路徑樹標(biāo)最短路徑樹標(biāo)記為記為粗體和藍粗體和藍色色.18更新結(jié)點的勢和即約代價更新結(jié)點的勢和即約代價1235400-7-11-12-10040120000-9-11為了得到新結(jié)點的為了得到新結(jié)點的勢，從老的勢中減勢，從老的勢中減去最短路徑距離去最短路徑距離.19沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)沿著最短路徑從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點點12354820201225285200013122-6從結(jié)點從結(jié)點2 發(fā)送流到發(fā)送流到結(jié)點結(jié)點5能發(fā)送多少流？能發(fā)送多少流？20更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)12354315201225285200013127-60-15從結(jié)點從結(jié)點2 發(fā)送發(fā)送5 個個單位的流到結(jié)點單位的流到結(jié)點6.21從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點從供應(yīng)結(jié)點發(fā)送流到需求結(jié)點12354315201225282000131270-15從結(jié)點從結(jié)點1發(fā)發(fā)送流到結(jié)點送流到結(jié)點522更新剩余網(wǎng)絡(luò)更新剩余網(wǎng)絡(luò)123542142012252720001313800-16從結(jié)點從結(jié)點1發(fā)送發(fā)送1 單位單位的流的流到結(jié)點到結(jié)點5.0結(jié)果的流是可行結(jié)果的流是可行的的,且也是最優(yōu)的且也是最優(yōu)的.23最終的最優(yōu)流最終的最優(yōu)流1235