连续最短路径算法

《连续最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、15.082J和6.855J连续最短路径算法初始代价和结点势123544122567000002初始容量和供应/需求1235410202025252030235-2-7-193选择供应结点和发现最短路径12354412256770688最短路径距离最短路径树标记为粗体和蓝色4更新结点势和即约代价1235441225670-7-8-8-60000635沿着最短路径从供应结点发送流到需求结点(沿着有即约代价势0的弧)1235410202025252030235-2-7-19从结点1发送7单位的流到结点3弧数是剩余容量.红色的弧有即约代价06更

2、新剩余网络1235410202025251330235-2-7-19弧(3,1)有即约代价07160如果一条弧添加到G(x),那么它有即约代价0且是红色的.在剩余网络中的弧将总有非负即约代价.7注释这点上，你应该选择源结点，然后找到从源结点到其他结点的最短路径，然后更新剩余网络.然而，在剩余网络中仍然有0即约代价的路径,且使用它们是有意义的.这种启发式方法在实践中非常有用.8沿着最短路径从供应结点发送流到需求结点12354102020252513305-2-19从结点1发送2个单位的流到结点4.7160回忆，红色的弧有即约代价是0.9更新

3、剩余网络12354102018252511305-2-19在1-3-4上，从结点1发送2单位的流到结点4.9160214010沿着最短路径从供应结点发送流到需求结点12354102018252511305-19从结点1发送流到结点5.902140应该发送多少流？11更新剩余网络123541020181425305-19从结点1到结点5发送11单位的流.2002140113-812选择供应结点以及选择最短路径1235410-7-8-8-600006300最短路径树标记为粗体和蓝色.在结点上的值是当前结点势.13更新结点的势和即约代价1235

4、410-7-8-8-603003300-11-11-90为了得到新结点的势，从老的势中减去最短路径距离.14沿着最短路径从供应结点发送流到需求结点123541020181425305从结点1发送流到结点520020113-8发送多少流？15更新剩余网络123548202012252852000131-8223-6从结点1发送2单位的流到结点516选择供应结点且寻找最短路径1235410-7-11-11-9030030000最短路径树标记为粗体和蓝色.17更新结点的势和即约代价1235400-7-11-12-10040120000-9-11

5、为了得到新结点的势，从老的势中减去最短路径距离.18沿着最短路径从供应结点发送流到需求结点12354820201225285200013122-6从结点2发送流到结点5能发送多少流？19更新剩余网络12354315201225285200013127-60-15从结点2发送5个单位的流到结点6.20从供应结点发送流到需求结点12354315201225282000131270-15从结点1发送流到结点521更新剩余网络123542142012252720001313800-16从结点1发送1单位的流到结点5.0结果的流是可行的,且也是最优

6、的.22最终的最优流1235410,820,62025,132520,2030,3235-2-7-1923最终最优结点势和即约代价1235400-7-11-12-100-40120流是在上界流是在下界.24