最大流问题的最短增广路径算法.ppt

,最大流问题的最短增广路径算法,最短增广路径,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(f)中的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,可进入弧将表示成粗线.,寻找最短 s-t 路径,6,4,2,4,2,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,如果需要，将在以后更新距离标号,寻找最短 s-t 路径,8,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,使用可进入弧从 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,这里是更新后的残留容量.,如果需要，将在以后更新距离标号,寻找最短 s-t 路径,10,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,使用可进入弧从 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,寻找最短 s-t 路径,13,2,2,2,4,2,2,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,搜索最短s-t 路径,15,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,搜索从 s 开始的最短 s-t 路径,1,1,3,2,3,1,如果没有从i出发的可进入弧，那么relabel(i) 且反向沿着从s出发的路径的一条弧.,搜索最短s-t 路径,16,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,搜索从 s 开始的最短 s-t 路径,1,1,3,2,3,1,如果没有从i出发的可进入弧，那么relabel(i) 且反向沿着从s出发的路径的一条弧.,2,5,3,2,搜索最短s-t 路径,17,2,2,2,4,2,2,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,搜索最短s-t 路径,19,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,搜索最短 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,搜索最短s-t 路径,21,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,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,