資源描述：
《圖論動畫-最短增廣路徑算法.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、15.082和6.855J最大流問題的最短增廣路徑算法最短增廣路徑4114212331s2453t這是初始網絡，加上弧的反向.2最短增廣路徑4114212331s2453t這是初始網絡和初始剩余網絡.3初始化距離4114212331s2453t結點標號從此以后將是距離標號.054321t453s2d(j)是在G(x)中的j到t的的最大的距離0221114可進入弧的表示4114212331s2453t弧(i,j)是可進入的，如果d(i)=d(j)+1.054321t453s2一條可進入弧的s-t路徑是最短路徑.
2、022111可進入弧將表示成粗線.54242尋找最短s-t路徑41121331s2453t使用可進入弧從s開始進行深度優(yōu)先搜索.054321t453s2022111下一步.發(fā)送流并更新剩余容量.21062422更新剩余容量41121331s2453t這里是更新的剩余容量.054321t453s2022111我們將會以后更新距離標號，如果需要.72422尋找最短s-t路徑41121331s2453t054321t453s2022111使用可進入弧從s開始進行深度優(yōu)先搜索.下一步.發(fā)送流并更新剩余容量.21082
3、22422更新剩余容量4111311s2453t054321t453s2022111這里是更新的剩余容量.我們將會以后更新距離標號，如果需要.9222422尋找最短s-t路徑4111311s2453t054321t453s2022111使用可進入弧從s開始進行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進入弧，那么relabel(i)且沿著到i的路徑反向.10222422更新距離和路徑4111311s2453t054321t45s2022111使用可進入弧從s開始進行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進入弧，那
4、么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.2311222422更新距離和路徑4111311s2453t054321ts2022111使用可進入弧從s開始進行深度優(yōu)先搜索.21如果沒有從i出發(fā)的可進入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.233s4512222422尋找最短s-t路徑4111311s2453t054321t2022111繼續(xù)從它離開的地方的路徑21如果路徑達到了t,那么發(fā)送流且更新剩余網絡.233s0214513222422更新剩余容量3111211s245
5、3t054321t202211121233s45這是更新的剩余容量.1114222422搜索最短s-t路徑3111211s2453t054321t202211121233s45搜索從s開始的最短s-t路徑113231如果沒有從i出發(fā)的可進入弧，那么relabel(i)且反向沿著從s出發(fā)的路徑的一條弧.15222422搜索最短s-t路徑3111211s2453t054321t202211121233s45搜索從s開始的最短s-t路徑113231如果沒有從i出發(fā)的可進入弧，那么relabel(i)且反向沿著從s出
6、發(fā)的路徑的一條弧.253216222422搜索最短s-t路徑3111211s2453t054321t0221112123s4511323123012235搜索從s開始的最短s-t路徑如果路徑達到了t,那么發(fā)送流且更新剩余網絡.17233412更新剩余容量311121s2453t054321t0221112123s45這是更新了的剩余容量113212323518233412搜索最短s-t路徑311121s2453t054321t0221112123s45搜索最短s-t路徑1132123235340123s1下一
7、步:更新剩余容量192342更新剩余容量21111s2453t054321t022111212345這是更新了的剩余容量222123235341s1202342搜索最短s-t路徑21111s2453t054321t022111212345更新距離標號和路徑222123235341s1234如果d(s)>n-1,那么沒有從s到t的路徑45652212342存在為最優(yōu)流的剩余容量21111s2453t054321t022111212345不存在在剩余網絡的s-t路徑222123235341s1456最小切割有S=
8、{s,2,5}.4565222
