图论动画-容量调整算法

《图论动画-容量调整算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、15.082和6.855J容量调整算法初始的代价和结点的势123544122567000002初始的容量和供应/需求1235410202025252030235-2-7-193设置=16.这开始-调整阶段1235410202025252030235-2-7-19我们从超额的结点发送流到亏损的结点.我们忽略容量的结点.4选择供应结点且寻找最短路径12354412256770688最短路径距离最短路径树标记为粗体和蓝色.5更新结点的势和即约代价1235441225670-7-8-8-60

2、000631为了更新结点的势，减去最短路径距离.6沿着在G(x,16)中的最短路径发送流123541从结点1发送流到结点5.202025252030235-2-7-19应该发送多少流？107更新剩余网络123541从结点1发送19单位的流到结点5.2020625130235-2-7010-19419198这就结束了16-调整阶段.123541当对某i有e(i)时，继续-调整阶段.对某些j有e(j)-时.存在从i到j的路径.20206251305-2-7010419199这个开始和结束8-调整

3、阶段123541当对某i有e(i)时，继续-调整阶段.对某些j有e(j)-时.存在从i到j的路径.20206251305-2-70104191910这个开始和结束4-调整阶段.12354120206251305-2-701041919如果存在容量至少是4和负即约代价的弧，我们怎么办？11选择一“大的超额”结点和寻找最短路径12354110-7-8-8-60006300最短路径树是标记为粗体和蓝色的.012更新结点势和即约代价12354100-7-8-8-60402001-11-12-10-4

4、为了更新结点势,减去最短路径距离.说明:低容量的弧可以有负即约代价.13沿在G(x,4)中的最短路径发送流.12354120206251305-2-701041919从结点1发送流到结点7应该发送多少流？14更新剩余网络123541162010251265-2-30641915从结点1发送4单位的流到结点30-744415这结束4-调整阶段.123541162010251265-2-3061915没有结点j有e(j)-4.044416开始2-调整阶段123541162010251265-2-3061

5、915没有结点j有e(j)-4.0444如果存在容量至少是4和负即约代价的弧，我们怎么办？17沿着最短路径发送流123541162010251265-2-30619150444从结点2发送流到结点4.应该发送多少？18更新剩余网络123541162010251265-2-30419150464从结点2发送2个单位的流到结点43019沿着最短路径发送流12354116201025126-30419150464从结点2发送流到结点330发送了多少流？20更新剩余网络12354113201325126-3

6、0119120794从结点2到结点3发送了3单位的流300021这结束了2-调整阶段.123541132013251260119120794我们是最优的吗？00022开始1-调整阶段.123541132013251260119120794饱和任何容量至少是1且有负代价的弧.000即约代价是负的23更新剩余网络1235411320132526012012-1794从结点3发送流到结点1.010注释:结点1现在是有亏损的结点.24更新剩余网络12354114201225270220130683从结点3发送

7、1单位的流到结点3.000这个流是最优的吗？25最终最优的流1235410,820,62025,132520,2030,3235-2-7-1926最终最优结点的势和即约代价1235400-7-11-12-100-40120流是在上界流是在下界.27