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

15.082和6.855J,最大流问题的最短增广路径算法,2,最短增广路径,4,1,1,4,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络，加上弧的反向.,3,最短增广路径,4,1,1,4,2,1,2,3,3,1,s,2,4,5,3,t,这是初始网络和初始剩余网络.,4,初始化距离,4,1,1,4,2,1,2,3,3,1,s,2,4,5,3,t,结点标号从此以后将是距离标号.,t,4,5,3,s,2,d(j)是在G(x)中的j到t的的最大的距离,0,2,2,1,1,1,5,可进入弧的表示,4,1,1,4,2,1,2,3,3,1,s,2,4,5,3,t,弧(i,j)是可进入的，如果d(i)=d(j)+1.,t,4,5,3,s,2,一条可进入弧的s-t路径是最短路径.,0,2,2,1,1,1,可进入弧将表示成粗线.,6,4,2,4,2,寻找最短s-t路径,4,1,1,2,1,3,3,1,s,2,4,5,3,t,使用可进入弧从s开始进行深度优先搜索.,t,4,5,3,s,2,0,2,2,1,1,1,下一步.发送流并更新剩余容量.,2,1,0,7,2,4,2,2,更新剩余容量,4,1,1,2,1,3,3,1,s,2,4,5,3,t,这里是更新的剩余容量.,t,4,5,3,s,2,0,2,2,1,1,1,我们将会以后更新距离标号，如果需要.,8,2,4,2,2,寻找最短s-t路径,4,1,1,2,1,3,3,1,s,2,4,5,3,t,t,4,5,3,s,2,0,2,2,1,1,1,使用可进入弧从s开始进行深度优先搜索.,下一步.发送流并更新剩余容量.,2,1,0,9,2,2,2,4,2,2,更新剩余容量,4,1,1,1,3,1,1,s,2,4,5,3,t,t,4,5,3,s,2,0,2,2,1,1,1,这里是更新的剩余容量.,我们将会以后更新距离标号，如果需要.,10,2,2,2,4,2,2,寻找最短s-t路径,4,1,1,1,3,1,1,s,2,4,5,3,t,t,4,5,3,s,2,0,2,2,1,1,1,使用可进入弧从s开始进行深度优先搜索.,2,1,如果没有从i出发的可进入弧，那么relabel(i)且沿着到i的路径反向.,11,2,2,2,4,2,2,更新距离和路径,4,1,1,1,3,1,1,s,2,4,5,3,t,t,4,5,s,2,0,2,2,1,1,1,使用可进入弧从s开始进行深度优先搜索.,2,1,如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.,2,3,12,2,2,2,4,2,2,更新距离和路径,4,1,1,1,3,1,1,s,2,4,5,3,t,t,s,2,0,2,2,1,1,1,使用可进入弧从s开始进行深度优先搜索.,2,1,如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.,2,3,3,s,4,5,13,2,2,2,4,2,2,寻找最短s-t路径,4,1,1,1,3,1,1,s,2,4,5,3,t,t,2,0,2,2,1,1,1,继续从它离开的地方的路径,2,1,如果路径达到了t,那么发送流且更新剩余网络.,2,3,3,s,0,2,1,4,5,14,2,2,2,4,2,2,更新剩余容量,3,1,1,1,2,1,1,s,2,4,5,3,t,t,2,0,2,2,1,1,1,2,1,2,3,3,s,4,5,这是更新的剩余容量.,1,1,15,2,2,2,4,2,2,搜索最短s-t路径,3,1,1,1,2,1,1,s,2,4,5,3,t,t,2,0,2,2,1,1,1,2,1,2,3,3,s,4,5,搜索从s开始的最短s-t路径,1,1,3,2,3,1,如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.,16,2,2,2,4,2,2,搜索最短s-t路径,3,1,1,1,2,1,1,s,2,4,5,3,t,t,2,0,2,2,1,1,1,2,1,2,3,3,s,4,5,搜索从s开始的最短s-t路径,1,1,3,2,3,1,如果没有从i出发的可进入弧，那么relabel(i)且反向沿着从s出发的路径的一条弧.,2,5,3,2,17,2,2,2,4,2,2,搜索最短s-t路径,3,1,1,1,2,1,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,s,4,5,1,1,3,2,3,1,2,3,0,1,2,2,3,5,搜索从s开始的最短s-t路径,如果路径达到了t,那么发送流且更新剩余网络.,18,2,3,3,4,1,2,更新剩余容量,3,1,1,1,2,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,s,4,5,这是更新了的剩余容量,1,1,3,2,1,2,3,2,3,5,19,2,3,3,4,1,2,搜索最短s-t路径,3,1,1,1,2,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,s,4,5,搜索最短s-t路径,1,1,3,2,1,2,3,2,3,5,3,4,0,1,2,3,s,1,下一步:更新剩余容量,20,2,3,4,2,更新剩余容量,2,1,1,1,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,4,5,这是更新了的剩余容量,2,2,2,1,2,3,2,3,5,3,4,1,s,1,21,2,3,4,2,搜索最短s-t路径,2,1,1,1,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,4,5,更新距离标号和路径,2,2,2,1,2,3,2,3,5,3,4,1,s,1,2,3,4,如果d(s)n-1,那么没有从s到t的路径,4,5,6,5,2,22,2,3,4,2,存在为最优流的