資源描述：
《最大流問題的最短增廣路徑算法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、最大流問題的最短增廣路徑算法最短增廣路徑24114212331s2453t這是初始網(wǎng)絡(luò)，加上反向邊.最短增廣路徑34114212331s2453t這是初始網(wǎng)絡(luò)和初始?xì)埩艟W(wǎng)絡(luò).初始化距離44114212331s2453t結(jié)點(diǎn)標(biāo)號從此以后將是距離標(biāo)號.054321t453s2d(j)是在G(f)中的j到t的的最短的距離022111可進(jìn)入弧的表示54114212331s2453t弧(i,j)是可進(jìn)入的，如果d(i)=d(j)+1.054321t453s2一條可進(jìn)入弧的s-t路徑是最短路徑.022111可進(jìn)入弧將表示成粗線.尋找最短s-t路徑64
2、24241121331s2453t使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.054321t453s2022111下一步.發(fā)送流并更新殘留容量.210更新殘留容量7242241121331s2453t這里是更新后的殘留容量.054321t453s2022111如果需要，將在以后更新距離標(biāo)號尋找最短s-t路徑8242241121331s2453t054321t453s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.下一步.發(fā)送流并更新殘留容量.210更新剩余容量92224224111311s2453t054321t453s2022111這里是
3、更新后的殘留容量.如果需要，將在以后更新距離標(biāo)號尋找最短s-t路徑102224224111311s2453t054321t453s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且沿著到i的路徑回溯.更新距離和路徑112224224111311s2453t054321t45s2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.23更新距離和路徑122224224111311s2453t054
4、321ts2022111使用可進(jìn)入弧從s開始進(jìn)行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.233s45尋找最短s-t路徑132224224111311s2453t054321t2022111繼續(xù)從它離開的地方的路徑21如果路徑達(dá)到了t,那么發(fā)送流且更新剩余網(wǎng)絡(luò).233s02145更新殘留容量142224223111211s2453t054321t202211121233s45這是更新后的殘留容量.11搜索最短s-t路徑152224223111211s2453t054321t20
5、2211121233s45搜索從s開始的最短s-t路徑113231如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.搜索最短s-t路徑162224223111211s2453t054321t202211121233s45搜索從s開始的最短s-t路徑113231如果沒有從i出發(fā)的可進(jìn)入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.2532搜索最短s-t路徑172224223111211s2453t054321t0221112123s4511323123012235搜索從s開始的最短s-t路
6、徑如果路徑達(dá)到了t,那么發(fā)送流且更新剩余網(wǎng)絡(luò).更新殘留容量18233412311121s2453t054321t0221112123s45這是更新了的殘留容量1132123235搜索最短s-t路徑19233412311121s2453t054321t0221112123s45搜索最短s-t路徑1132123235340123s1下一步:更新殘留容量更新殘留容量20234221111s2453t054321t022111212345這是更新了的殘留容量222123235341s1搜索最短s-t路徑21234221111s2453t05432
7、1t022111212345更新距離標(biāo)號和路徑222123235341s1234如果d(s)>n-1,那么沒有從s到t的路徑45652得到最大流時的殘留網(wǎng)絡(luò)22234221111s2453t054321t022111212345殘留網(wǎng)絡(luò)中找不到s-t路徑222123235341s1456最小割是S={s,2,5}.45652
