图论动画-连续最短路径算法.ppt

15.082J和6.855J,连续最短路径算法,2,初始代价和结点势,1,2,3,5,4,4,1,2,2,5,6,7,0,0,0,0,0,3,初始容量和供应/需求,1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,4,选择供应结点和发现最短路径,1,2,3,5,4,4,1,2,2,5,6,7,7,0,6,8,8,最短路径距离,最短路径树标记为粗体和蓝色,5,更新结点势和即约代价,1,2,3,5,4,4,1,2,2,5,6,7,0,-7,-8,-8,-6,0,0,0,0,6,3,6,沿着最短路径从供应结点发送流到需求结点(沿着有即约代价势0的弧),1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,从结点1发送7单位的流到结点3,弧数是剩余容量.红色的弧有即约代价0,7,更新剩余网络,1,2,3,5,4,10,20,20,25,25,13,30,23,5,-2,-7,-19,弧(3,1)有即约代价0,7,16,0,如果一条弧添加到G(x),那么它有即约代价0且是红色的.,在剩余网络中的弧将总有非负即约代价.,8,注释,这点上，你应该选择源结点，然后找到从源结点到其他结点的最短路径，然后更新剩余网络.然而，在剩余网络中仍然有0即约代价的路径,且使用它们是有意义的.这种启发式方法在实践中非常有用.,9,沿着最短路径从供应结点发送流到需求结点,1,2,3,5,4,10,20,20,25,25,13,30,5,-2,-19,从结点1发送2个单位的流到结点4.,7,16,0,回忆，红色的弧有即约代价是0.,10,更新剩余网络,1,2,3,5,4,10,20,18,25,25,11,30,5,-2,-19,在1-3-4上，从结点1发送2单位的流到结点4.,9,16,0,2,14,0,11,沿着最短路径从供应结点发送流到需求结点,1,2,3,5,4,10,20,18,25,25,11,30,5,-19,从结点1发送流到结点5.,9,0,2,14,0,应该发送多少流？,12,更新剩余网络,1,2,3,5,4,10,20,18,14,25,30,5,-19,从结点1到结点5发送11单位的流.,20,0,2,14,0,11,3,-8,13,选择供应结点以及选择最短路径,1,2,3,5,4,1,0,-7,-8,-8,-6,0,0,0,0,6,3,0,0,最短路径树标记为粗体和蓝色.,在结点上的值是当前结点势.,14,更新结点的势和即约代价,1,2,3,5,4,1,0,-7,-8,-8,-6,0,3,0,0,3,3,0,0,-11,-11,-9,0,为了得到新结点的势，从老的势中减去最短路径距离.,15,沿着最短路径从供应结点发送流到需求结点,1,2,3,5,4,10,20,18,14,25,30,5,从结点1发送流到结点5,20,0,2,0,11,3,-8,发送多少流？,16,更新剩余网络,1,2,3,5,4,8,20,20,12,25,28,5,20,0,0,13,1,-8,2,2,3,-6,从结点1发送2单位的流到结点5,17,选择供应结点且寻找最短路径,1,2,3,5,4,1,0,-7,-11,-11,-9,0,3,0,0,3,0,0,0,0,最短路径树标记为粗体和蓝色.,18,更新结点的势和即约代价,1,2,3,5,4,0,0,-7,-11,-12,-10,0,4,0,1,2,0,0,0,0,-9,-11,为了得到新结点的势，从老的势中减去最短路径距离.,19,沿着最短路径从供应结点发送流到需求结点,1,2,3,5,4,8,20,20,12,25,28,5,20,0,0,13,1,2,2,-6,从结点2发送流到结点5,能发送多少流？,20,更新剩余网络,1,2,3,5,4,3,15,20,12,25,28,5,20,0,0,13,1,2,7,-6,0,-1,5,从结点2发送5个单位的流到结点6.,21,从供应结点发送流到需求结点,1,2,3,5,4,3,15,20,12,25,28,20,0,0,13,1,2,7,0,-1,5,从结点1发送流到结点5,22,更新剩余网络,1,2,3,5,4,2,14,20,12,25,27,20,0,0,13,1,3,8,0,0,-1,6,从结点1发送1单位的流到结点5.,0,结果的流是可行的,且也是最优的.,23,最终的最优流,1,2,3,5,4,10,8,20,6,20,25,13,25