容量调整算法.ppt

15.082 和 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,设置 = 16. 这开始 -调整阶段,1,2,3,5,4,10,20,20,25,25,20,30,23,5,-2,-7,-19,我们从超额 的结点发送流到亏损 的结点.,我们忽略容量 的结点.,5,选择供应结点且寻找最短路径,1,2,3,5,4,4,1,2,2,5,6,7,7,0,6,8,8,最短路径距离,最短路径树标记为粗体和蓝色.,6,更新结点的势和即约代价,1,2,3,5,4,4,1,2,2,5,6,7,0,-7,-8,-8,-6,0,0,0,0,6,3,1,为了更新结点的势，减去最短路径距离.,7,沿着在G(x,16)中的最短路径发送流,1,2,3,5,4,1,从结点1发送流到结点5.,20,20,25,25,20,30,23,5,-2,-7,-19,应该发送多少流？,10,8,更新剩余网络,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,9,这就结束了 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,10,这个开始和结束 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,11,这个开始和结束 4-调整阶段.,1,2,3,5,4,1,20,20,6,25,1,30,5,-2,-7,0,10,4,19,19,如果存在容量至少是 4 和负即约代价的弧，我们怎么办？,12,选择一 “大的超额” 结点和寻找最短路径,1,2,3,5,4,1,1,0,-7,-8,-8,-6,0,0,0,6,3,0,0,最短路径树是标记为粗体和蓝色的.,0,13,更新结点势和即约代价,1,2,3,5,4,1,0,0,-7,-8,-8,-6,0,4,0,2,0,0,1,-11,-12,-10,-4,为了更新结点势,减去最短路径距离.,说明: 低容量的弧可以有负即约代价.,14,沿在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,应该发送多少流？,15,更新剩余网络,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,16,这结束 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,17,开始 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 和负即约代价的弧，我们怎么办？,18,沿着最短路径发送流,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.,应该发送多少？,19,更新剩余网络,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,20,沿着最短路径发送流,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,发送了多少流？,21,更新剩余网络,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,22,这结束了2-调整阶段.,1,2,3,5,4,1,13,20,13,25,1,26,0,1,19,12,0,7,9,4,我们是最优的吗？,0,0,0,23,开始 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,即约代价是负的,24,更新剩余网络,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现在是有亏损的结点.,25,更新剩余网络,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,这个流是最优的吗？,26,最终最优的流,1,2,3,5,4,10,8,20,6,20,25,13,25,20,20,30,3,23,5,-2,-7,-19,27,最终最优结点的势和即约代价,1,2,3,5,4,0,0,-7,-11,-12,-10,0,-4,0,1,2,0,流是在上界,流是在下界.,