【2017年整理】最短路与网络流.ppt

第八章 图与网络分析;第一讲： 最短路问题;最短路算法中1959年由 （狄克斯特洛）提出的 算法被公认为是目前最好的方法，我们称之为 算 法。下面通过例子来说明此法的基本思想。;下求 到 的最短路：;可能最短路为;表明走出 后走向 的最短路目前看是 ，最优距离 是4 。;3）接着往下考察，有三条路可走： ;4）接着往下考察，有四条路可走： ;5）接着往下考察，有四条路可走： ;6）接着往下考察，有四条路可走： ;7）接着往下考察，有四条路可走： ;最后，从 逆寻粗线到 ，得最短路：; 第二讲：最短路问题的两个应用;项目;解：把这个问题化为最短路问题。;边 上的数字表示第i年初购进设备，一直使用到第j年 初所需支付的购买费、维修的全部费用（可由表8-2计算得 到）。;⑴ ;①;⑸;①;①;例13 (选址问题P265 ) 已知某地区的交通网络如图8-37所示， 其中点代表居民小区，边代表公路，为小区间公路距离，问区 中心医院应建在哪个小区，可使离医院最远的小区居民就诊时 所走的路程最近？;即为所求。;⑶;⑷;⑸;⑹; ;三. Floyd （佛洛伊德）算法;例14/P266; 中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。 ; 中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。 ;注意到：;注意到：;说明所有点经过 并没有缩短路程。;只有一个新增元素;表示任意两点间的最短路长及其路径。 ;第二讲 最大流问题;① 分别称 为发点、收点。其余的点称为中间点。;④容量限制 条件： 对每一边上都有 ;⑥ 可增广链：是指从 到 有一条链，此链上有 ≤ 的现象出现。（非饱和链） ;b) 接着检查与相邻接的点 ， ， 。 已饱和，流量不 可再增。再检查 ，可调整量为 4-2=2，可提供量+∞，取 调整量;给 标号 ，其中 表示 的所调整量2来自 ，且 为正向流（向前流） 。;调整量为;可令调整量为;f) 下面检查与 相邻接且未标号的点 ，同理，调整量：;2）调整流量：从 到 所画出的彩线即为可增广链。沿 该可增广链，从 倒推，标“＋”号的在实际流量上加上 该调整量，标“－”符号的在实际流量上减去该调整量。完 成调整过程。;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;重新开始标号，寻找可增广链。当标到 时，与 ， 相 邻接的点 ， ， 都不满足标号条件，标号无法继续，且 没有完成标号。此时最大流量即为所求。;第三讲：最大流问题的应用;2．匹配：;3．最大匹配问题：;求最大匹配问题方法很多，以前学过交替链法，下介绍 最大流法。即所谓;二部图中最大匹配问题，可以转化为最大流问题求解。在 二部图中增加两个新点 分别作为发点，收点。并用 有向边把它们与原二部图中顶点相连，令全部边上的容量 均为1。当网络流达到最大时，如果 上的流量为1， 就让 作 工作，此即为最大匹配方案。;第一次标号。;第二次标号。;第三次标号。;调整。;第四次标号。;调整;第五次标号。;标号过程已无法再继续。流量为1的画彩线。;工人;应用2;解：设 ， 分别表示每项运输任务的出发日期及 完成日期（i=1，2，3，4，5）则由表8-5和表8-6 知：;任务;任务;任务;作一个二部图，点集｛X｝和｛Y｝都表示这5项任务，两 点间有连线的条件是第i件任务完成后可赶上作第j件任务。 有连线即有匹配，连线越多（匹配数越大）一只船重复使 用次数多，使用船只数就越少。最大的匹配就是用最少的 船。;任务;此表示共两只船可完成任务： ; 第四讲：最小费用最大流;下面通过例子来说明带负权的网络的最短路求法：逐次 逼近法：;①;①;①;①;①;①;①;①; §5 最小费用流的问题;特别的，当最大流不惟一时，在所有最大流中求一个流f,使 总费用最低。;求最费用最大流的基本思想是：从零流 开 始，以费用作为边的长度