图论动画-最短增广路径算法.ppt

《图论动画-最短增广路径算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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开始进行深度优先搜索.054321t453s2022111下一步.发送流并更新剩余容量.21062422更新剩余容量41121331s2453t这里是更新的剩余容量.054321t453s2022111我们将会以后更新距离标号，如果需要.72422寻找最短s-t路径41121331s2453t054321t453s2022111使用可进入弧从s开始进行深度优先搜索.下一步.发送流并更新剩余容量.21082

3、22422更新剩余容量4111311s2453t054321t453s2022111这里是更新的剩余容量.我们将会以后更新距离标号，如果需要.9222422寻找最短s-t路径4111311s2453t054321t453s2022111使用可进入弧从s开始进行深度优先搜索.21如果没有从i出发的可进入弧，那么relabel(i)且沿着到i的路径反向.10222422更新距离和路径4111311s2453t054321t45s2022111使用可进入弧从s开始进行深度优先搜索.21如果没有从i出发的可进入弧，那

4、么relabel(i)且反向沿着从s出发的路径的一条弧.2311222422更新距离和路径4111311s2453t054321ts2022111使用可进入弧从s开始进行深度优先搜索.21如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.233s4512222422寻找最短s-t路径4111311s2453t054321t2022111继续从它离开的地方的路径21如果路径达到了t,那么发送流且更新剩余网络.233s0214513222422更新剩余容量3111211s245

5、3t054321t202211121233s45这是更新的剩余容量.1114222422搜索最短s-t路径3111211s2453t054321t202211121233s45搜索从s开始的最短s-t路径113231如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.15222422搜索最短s-t路径3111211s2453t054321t202211121233s45搜索从s开始的最短s-t路径113231如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出

6、发的路径的一条弧.253216222422搜索最短s-t路径3111211s2453t054321t0221112123s4511323123012235搜索从s开始的最短s-t路径如果路径达到了t,那么发送流且更新剩余网络.17233412更新剩余容量311121s2453t054321t0221112123s45这是更新了的剩余容量113212323518233412搜索最短s-t路径311121s2453t054321t0221112123s45搜索最短s-t路径1132123235340123s1下一

7、步:更新剩余容量192342更新剩余容量21111s2453t054321t022111212345这是更新了的剩余容量222123235341s1202342搜索最短s-t路径21111s2453t054321t022111212345更新距离标号和路径222123235341s1234如果d(s)>n-1,那么没有从s到t的路径45652212342存在为最优流的剩余容量21111s2453t054321t022111212345不存在在剩余网络的s-t路径222123235341s1456最小切割有S=

8、{s,2,5}.4565222