连续最短路径算法ppt课件

1、15.082J 和和 6.855J延续最短途径算法延续最短途径算法初始代价和结点势初始代价和结点势12354412256700000初始容量和供应初始容量和供应/需求需求1235410202025252030235-2-7-19选择供应结点和发现最短途径选择供应结点和发现最短途径12354412256770688最短途径间隔最短途径树最短途径树标志为粗体标志为粗体和蓝色和蓝色更新结点势和即约代价更新结点势和即约代价1235441225670-7-8-8-6000063沿着最短途径从供应结点发送流到需求结沿着最短途径从供应结点发送流到需求结点点 (沿着有即约代价势沿着有即约代价势 0 的弧的弧)

2、1235410202025252030235-2-7-19从结点从结点1发发送送7单位的单位的流到结点流到结点3弧数是剩余容弧数是剩余容量量.红色的弧有即红色的弧有即约代价约代价 0更新剩余网络更新剩余网络1235410202025251330235-2-7-19弧弧(3,1) 有即有即约代价约代价07160假设一条弧添假设一条弧添加到加到 G(x), 那么那么它有即约代价它有即约代价 0且是红色的且是红色的.在剩余网络中的在剩余网络中的弧将总有非负即弧将总有非负即约代价约代价.注释注释这点上，他应该选择源结点，然后找到从源结点到其他这点上，他应该选择源结点，然后找到从源结点到其他结点的最短途

3、径，然后更新剩余网络结点的最短途径，然后更新剩余网络.然而，在剩余网络中依然有然而，在剩余网络中依然有0即约代价的途径即约代价的途径,且运用它且运用它们是有意义的们是有意义的. 这种启发式方法在实际中非常有用这种启发式方法在实际中非常有用.沿着最短途径从供应结点发送流到需求结沿着最短途径从供应结点发送流到需求结点点12354102020252513305-2-19从结点从结点1发送发送2个单位的流到个单位的流到结点结点4.7160回想，红色的弧回想，红色的弧有即约代价是有即约代价是0.更新剩余网络更新剩余网络12354102018252511305-2-19在在1-3-4上，从结上，从结点点1

4、发送发送2单位的单位的流到结点流到结点 4.91602140沿着最短途径从供应结点发送流到需求结沿着最短途径从供应结点发送流到需求结点点12354102018252511305-19从结点从结点1发送流到发送流到结点结点5.902140应该发送多应该发送多少流？少流？更新剩余网络更新剩余网络123541020181425305-19从结点从结点1到结点到结点5发发送送11 单位的流单位的流.2002140113-8选择供应结点以及选择最短途径选择供应结点以及选择最短途径1235410-7-8-8-600006300最短途径树标志最短途径树标志为粗体和蓝色为粗体和蓝色.在结点上的值是在结点上的值

5、是当前结点势当前结点势.更新结点的势和即约代价更新结点的势和即约代价1235410-7-8-8-603003300-11-11-90为了得到新结点为了得到新结点的势，从老的势的势，从老的势中减去最短途径中减去最短途径间隔间隔.沿着最短途径从供应结点发送流到需求结沿着最短途径从供应结点发送流到需求结点点123541020181425305从结点从结点1发送流到结发送流到结点点520020113-8发送多少流？发送多少流？更新剩余网络更新剩余网络123548202012252852000131-8223-6从结点从结点 1 发送发送2 单位的流到结点单位的流到结点5选择供应结点且寻觅最短途径选择供

6、应结点且寻觅最短途径1235410-7-11-11-9030030000最短途径树标最短途径树标志为粗体和蓝志为粗体和蓝色色.更新结点的势和即约代价更新结点的势和即约代价1235400-7-11-12-10040120000-9-11为了得到新结点的为了得到新结点的势，从老的势中减势，从老的势中减去最短途径间隔去最短途径间隔.沿着最短途径从供应结点发送流到需求结沿着最短途径从供应结点发送流到需求结点点12354820201225285200013122-6从结点从结点2 发送流到发送流到结点结点5能发送多少流？能发送多少流？更新剩余网络更新剩余网络12354315201225285200013127-60-15从结点从结点2 发送发送5 个个单位的流到结点单位的流到结点6.从供应结点发送流到需求结点从供应结点发送流到需求结点12354315201225282000131270-15从结点从结点1发发送流到结点送流到结点5更新剩余网络更新剩余网络123542142012252720001313800-16从结点从结点1发送发送1 单位单位的流到结点的流到结点5.0结果的流是可行结果的流是可行的的,且也是最优的且也是最优的.最终的最优流最终的最优流1235