资源描述
Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,*,15.082,和,6.855J,容量调整算法,初始的代价和结点的势,1,2,3,5,4,4,1,2,2,5,6,7,0,0,0,0,0,2,初始的容量和供应,/,需求,1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,3,设置,= 16.,这开始,-,调整阶段,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,1,为了更新结点的势，减去最短路径距离,.,6,沿着在,G(x,16),中的最短路径发送流,1,2,3,5,4,1,从结点,1,发送流到结点,5.,20,20,25,25,20,30,23,5,-2,-7,-19,应该发送多少流？,10,7,更新剩余网络,1,2,3,5,4,1,从结点,1,发送,19,单位的流到结点,5.,20,20,6,25,1,30,23,5,-2,-7,0,10,-19,4,19,19,8,这就结束了,16-,调整 阶段,.,1,2,3,5,4,1,当对某,i,有,e(i) ,时，继续,-,调整阶段,.,对某些,j,有,e(j) ,-,时,.,存在从,i,到,j,的路径,.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,9,这个开始和结束,8-,调整阶段,1,2,3,5,4,1,当对某,i,有,e(i) ,时，继续,-,调整阶段,.,对某些,j,有,e(j) ,-,时,.,存在从,i,到,j,的路径,.,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,10,这个开始和结束,4-,调整阶段,.,1,2,3,5,4,1,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,如果存在容量至少是,4,和负即约代价的弧，我们怎么办？,11,选择一,“,大的超额,”,结点和寻找最短路径,1,2,3,5,4,1,1,0,-7,-8,-8,-6,0,0,0,6,3,0,0,最短路径树是标记为粗体和蓝色的,.,0,12,更新结点势和即约代价,1,2,3,5,4,1,0,0,-7,-8,-8,-6,0,4,0,2,0,0,1,-11,-12,-10,-4,为了更新结点势,减去最短路径距离,.,说明,:,低容量的弧可以有负即约代价,.,13,沿在,G(x,4),中的最短路径发送流,.,1,2,3,5,4,1,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,从结点,1,发送流到结点,7,应该发送多少流？,14,更新剩余网络,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,4,19,15,从结点,1,发送,4,单位的流到结点,3,0,-7,4,4,4,15,这结束,4-,调整阶段,.,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,19,15,没有结点,j,有,e(j), -4.,0,4,4,4,16,开始,2-,调整阶段,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,19,15,没有结点,j,有,e(j), -4.,0,4,4,4,如果存在容量至少是,4,和负即约代价的弧，我们怎么办？,17,沿着最短路径发送流,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,6,19,15,0,4,4,4,从结点,2,发送流到结点,4.,应该发送多少？,18,更新剩余网络,1,2,3,5,4,1,16,20,10,25,1,26,5,-2,-3,0,4,19,15,0,4,6,4,从结点,2,发送,2,个单位的流到结点,4,3,0,19,沿着最短路径发送流,1,2,3,5,4,1,16,20,10,25,1,26,-3,0,4,19,15,0,4,6,4,从结点,2,发送流到结点,3,3,0,发送了多少流？,20,更新剩余网络,1,2,3,5,4,1,13,20,13,25,1,26,-3,0,1,19,12,0,7,9,4,从结点,2,到结点,3,发送了,3,单位的流,3,0,0,0,21,这结束了,2-,调整阶段,.,1,2,3,5,4,1,13,20,13,25,1,26,0,1,19,12,0,7,9,4,我们是最优的吗？,0,0,0,22,开始,1-,调整阶段,.,1,2,3,5,4,1,13,20,13,25,1,26,0,1,19,12,0,7,9,4,饱和任何容量至少是,1,且有负代价的弧,.,0,0,0,即约代价是负的,23,更新剩余网络,1,2,3,5,4,1,13,20,13,25,26,0,1,20,12,-1,7,9,4,从结点,3,发送流到结点,1.,0,1,0,注释,:,结点,1,现在是有亏损的结点,.,24,更新剩余网络,1,2,3,5,4,1,14,20,12,25,27,0,2,20,13,0,6,8,3,从结点,3,发送,1,单位的流到结点,3.,0,0,0,这个流是最优的吗？,25,最终最优的流,1,2,3,5,4,10,8,20,6,20,25,13,25,20,20,30,3,23,5,-2,-7,-19,26,最终最优结点的势和即约代价,1,2,3,5,4,0,0,-7,-11,-12,-10,0,-4,0,1,2,0,流是在上界,流是在下界,.,27,
展开阅读全文