《图论动画-最短增广路径算法》由会员分享，可在线阅读，更多相关《图论动画-最短增广路径算法（21页珍藏版）》请在金锄头文库上搜索。
1、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) 是 可进
2、入的，如果 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
3、,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,使用可
4、进入弧从 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
5、,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,搜
6、索最短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出发的路径的一
7、条弧.,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
8、,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,存在为最优流的剩余容量,2,1,1,1,1,s,2,4,5,3,t,t,0,2,2,1,1,1,2,1,2,3,4,5,不存在在剩余网络的s-t 路径,2,2,2,1,2,3,2,3,5,3,4,1,s,1,4,5,6,最小切割有S = s, 2, 5.,4,5,6,5,2,
