最短路与网络流.ppt

1、第八章 图与网络分析,最短路问题 最短路的应用,第一讲： 最短路问题,最短路问题是网络理论中应用最广泛的问题之一。许多优 化问题都可以使用这个模型，如设备更新、管道的铺设、 线路的安排、厂区的布局等。,最短路问题的一般提法是：设 为连通图，图中 各边 有权 ( 表示 ， 之间没有边）, 为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即：,最小。,最短路算法中1959年由 （狄克斯特洛）提出的 算法被公认为是目前最好的方法，我们称之为 算 法。下面通过例子来说明此法的基本思想。,条件：所有的权数,思路：逐步探寻。,下求 到 的最短路：,1）从 出发，向 走。首先，从 到 的

2、距离为0，给 标号（0）。画第一个弧。（表明已 标号，或已走出 ）,从 出发，只有两条路可走 ，其距离为,2）,可能最短路为, 给 划成粗线。, 划第二个弧。, 给 标号（4）。,表明走出 后走向 的最短路目前看是 ，最优距离 是4 。,现已考察完毕第二个圈内的路，或者说，已完成 的标号。,3）接着往下考察，有三条路可走：,可选择的最短路为, 给 划成粗线。, 划第3个弧。, 给 标号（6）。,4）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第4个弧。, 给 标号（8）。,5）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第5个弧。, 给 标号

3、（9）。,6）接着往下考察，有四条路可走：,可选择的最短路为, 给 划成粗线。, 划第6个弧。, 给 标号（13）。,7）接着往下考察，有四条路可走：,可选择的最短路为, 同时给 划成粗线。, 分别给 标号（14）。,最后，从 逆寻粗线到 ，得最短路：,长度为15。,第二讲：最短路问题的两个应用,最短路问题在图论应用中处于很重要的地位，下面举两个实 际应用的例子。 例12/P264 设备更新问题 某工厂使用一台设备，每年年初工厂要作出决定：继续使 用，购买新的？如果继续使用旧的，要负维修费；若要购买 一套新的，要负购买费。试确定一个5年计划，使总支出最小,若已知设备在各年的购买费，及不同机器役

4、龄时的残值与 维修费，如表8-2所示.,表8-2,解：把这个问题化为最短路问题。,用点 表示第i年初购进一台新设备，虚设一个点 ，表示第 5年底。,边 表示第i年购进的设备一直使用到第j年初（即第j-1 年底）。,边 上的数字表示第i年初购进设备，一直使用到第j年 初所需支付的购买费、维修的全部费用（可由表8-2计算得 到）。,这样设备更新问题就变为：求从 到 的最短路问题.,给 划成彩线。,给 划成彩线。,给 划成彩线。,给 划成彩线。,给 划成彩线。,计算结果：最短路,最短路路长为49。,即：在第一年、第三年初各购买一台新设备为最优决策。 这时5年的总费用为49。,例13 (选址问题P26

5、5 ) 已知某地区的交通网络如图8-37所示， 其中点代表居民小区，边代表公路，为小区间公路距离，问区 中心医院应建在哪个小区，可使离医院最远的小区居民就诊时 所走的路程最近？,解 求中心的问题。 解决方法：先求出 到 其它各点的最短路长 如,再求,即为所求。,比如求,给 划成彩线。,给 划成彩线。,给 标号20。,给 划成彩线。,给 标号30。,分别给 划成彩线。,分别给 标号33。,给 划成彩线。,给 标号63。,其它计算结果见下表：,表 8.1,由于 最小，所以医院应建在 ，此时离医院最 远的小区 距离为48。,三. Floyd （佛洛伊德）算法,这里介绍得Floyd（1962年）可直接

6、求出网络中任意两 点间的最短路。,令网络中的权矩阵为,其中,当,其他,算法基本步骤为：, 输入权矩阵,例14/P266, 计算,其中,例如：,中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。,中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。,在放开 的基础上，再放开,注意到：,在放开 点的基础上，再放开 考察最短路。,注意到：,说明所有点经过 并没有缩短路程。,只有一个新增元素,表示任意两点间的最短路长及其路径。,第二讲 最大流问题,最大流问题是一类应用极为广泛的问题，例如在交通运输 网络中有人流、车流、货

7、物流、供水系统中有水流，金融 系统中有现金流，通信系统中有信息流，等等。,一 有关概念：,例：下图是输油管道网， 为起点， 为终点， ， ， ， 为中转站，边上的数字表示该管道的最大输油能 力（也称容量），记为 ，问应如何安排各管道输油量， 才能使从到的总输油量最大？, 分别称 为发点、收点。其余的点称为中间点。, 每一个边上都给定一个容量的网络称为容量网络，记,的每一个边上都给定一个实际流量 的网络称为给 定了网络一个流。,容量限制 条件： 对每一边上都有,平衡条件： a) 中间点： 流入量=流出量。 b) 发收点： 发出流量=汇入流量。,若 ，称边 是饱和边。, 可增广链：是指从 到 有一

8、条链，此链上有 的现象出现。（非饱和链）,这种流称为可行流。上图就是一个可行流。使流量达到 最大的流称为最大流 。,二 求解最大流：,先给标号 （，+），其中意思是流入的结点，现没 有，纯属一个符号。+表示的流出量。因它上面没有结点 来控制它，故设为+.,1） 寻找可增广链：,b) 接着检查与相邻接的点 ， ， 。 已饱和，流量不 可再增。再检查 ，可调整量为 4-2=2，可提供量+，取 调整量,给 标号 ，其中 表示 的所调整量2来自 ，且 为正向流（向前流） 。,同理，给 标号,下对已标号点（可望调整点）接着向下检查。 已饱 和。再检查与 相邻接且未标号的点,调整量为,给 标号为,d) 检

9、查与 相邻接且未标号的点 ， 。而 对 来讲是流 入，现欲增加流出量，应压缩 的流入量，只要的流入量,可令调整量为,给 标号为,表示可控量，反方向流量。,f) 下面检查与 相邻接且未标号的点 ，同理，调整量：,给 标号为,g) 最后，给 标号,2）调整流量：从 到 所画出的彩线即为可增广链。沿 该可增广链，从 倒推，标“”号的在实际流量上加上 该调整量，标“”符号的在实际流量上减去该调整量。完 成调整过程。,重新开始标号，寻找可增广链。当标到 时，与 ， 相 邻接的点 ， ， 都不满足标号条件，标号无法继续，且 没有完成标号。此时最大流量即为所求。,第三讲：最大流问题的应用,1. 最大匹配问题

10、, 二部图（也叫二分图）,图G= (V, E), 若V=XY且XY=，使得E中每一条边 的两个端点必有一个属于X，另一个属于Y，则称G为二 部图。记G=（X，Y，E），或G=（X，E，Y）。,2匹配：,对给定的二部图G =（X，Y，E），若有ME，且M中 任意两条边都没有公共端点，则称M为G的一个匹配 （也称对集）。,既满足：一个人只多做一件工作，每件工作只多由一人来 做。即为工作集与工人集之间的一个匹配。,3最大匹配问题：, 表示G中所有的匹配集，即, =M | M为G的匹配集,|M|表示M的边数，若存在 M0 使对任意的M，有,则称 M0 是G 的最大匹配。,注：G中最大匹配方案可能不唯一

11、。,饱和点：M中任意边的端点称为（关于M的）饱和点， G中其他顶点称为非饱和点。,求最大匹配问题方法很多，以前学过交替链法，下介绍 最大流法。即所谓,2。多端网络问题：,例16/P-274 设有5位待业者，5项工作，他们各自能胜任 工作的情况如图8-47所示，要求设计一个就业方案，使尽 量多的人能就业。,其中,表示工人。,表示工作。,二部图中最大匹配问题，可以转化为最大流问题求解。在 二部图中增加两个新点 分别作为发点，收点。并用 有向边把它们与原二部图中顶点相连，令全部边上的容量 均为1。当网络流达到最大时，如果 上的流量为1， 就让 作 工作，此即为最大匹配方案。,第一次标号。,调整,第二

12、次标号。,再调整。,第三次标号。,调整。,第四次标号。,调整,第五次标号。,标号过程已无法再继续。流量为1的画彩线。,工人,分别作,故最多安排四个人工作。,应用2,例/习题8.21/P-282：现有5批货物，每批只需一条船装 运，要由 ， 所在地域运往 ， ， 地域。至于货物 从 ， 运向 ， ， 三点何处都一样，每批货物出 发日期如表8-5，航船行所需天数如表8-6。船只空载和 重载时航行时间相同。要求制定一个计划，在半个月内用 最少的船只把5批货物运过去。,表8-5（出发日期）,表8-6（航行天数）,解：设 ， 分别表示每项运输任务的出发日期及 完成日期（i=1，2，3，4，5）则由表8-

13、5和表8-6 知：,要想用较少的船只在115天内完成任务，关键是自上一任 务到达的时间加上返回的时间能否赶上下一个任务出发的 时间。若能，则一只船就能完成两批货物的运输任务。,以下试运行：,5号,7号,8号回,10号,表8-6（航行天数）,8号,12号回,13号,14号回,10号,3号,表8-6（航行天数）,1号,13号,5号回,共两只船在13号以前就把5批货物全部运了出去。,是否最优？一只船可行否？如何解决？,作一个二部图，点集X和Y都表示这5项任务，两 点间有连线的条件是第i件任务完成后可赶上作第j件任务。 有连线即有匹配，连线越多（匹配数越大）一只船重复使 用次数多，使用船只数就越少。最

14、大的匹配就是用最少的 船。,表8-6（航行天数）,此表示共两只船可完成任务：,：,：,解不唯一。,第四讲：最小费用最大流,大家知道， 法求最短路只适应于权 0的情况， 当网络中出现负权时，此法失效，如：,一。带负权的最短路问题：,求 到 的最短路。,下面通过例子来说明带负权的网络的最短路求法：逐次 逼近法：,1给标号 （0）。画弧。, 给 划成彩线。, 划第二个弧。, 给 标号（-3）。, 给 划成彩线。, 划第三个弧。, 给 标号（1）。, 给 划成彩线。, 划第四个弧。, 给 标号（2）。, 给 划成彩线。, 划第五个弧。, 给 再次标号（0）。,去掉 彩线。, 分别给 划成彩线。, 划第

15、六个弧。, 分别给 标号（6）。, 给 划成彩线。, 划第七个弧。, 给 标号（10）。, 给 划成彩线。,到达 已经无负权，路程不可能再减少。, 给 标号（9）。,最短路径为：,距离：10。,5 最小费用流的问题,前两节主要讲了两个问题：最短路问题和最大流问题。下 面介绍网络中二者的结合问题：最小费用流的问题。,问题的提出是这样的：在一个关于流的网络中，人们不仅 需要流达到一定的数量，（甚至达到最大，即最大流）而 且每一个流量要有一定的费用，流所走的路线不一样，单 位费用不一样。同样数量的流量，可能走的路线不一样， 总的费用不一样。从而在限定网络流的基础上，让流沿那 些边走，能使总的费用最小

16、（这里的最小费用问题又看成 最短路问题）。,特别的，当最大流不惟一时，在所有最大流中求一个流f,使 总费用最低。,流量的费用 ，记为,用规划语言可以这样描述：若给定容量网络,G=（V，E，C）,除给定每个边,上的容量,外，还给定,G=（V，E，C，D）,若给定G的一个可行流 , 在总的流量,（常数）下使,求最费用最大流的基本思想是：从零流 开 始，以费用作为边的长度，用求最短路的方法，求出可增 广链，调整流量，使其流量逐步达到要求的数量。,下通过例子来说明。,例：在图8-55所示的网络中，求流量为10的最小费用流。 边上括号内为 。,先假设此网络是空架子，即0-流。然后，逐步调整流量 到10，在什么路线上增加流量？在费用最小的路线上调 流量。为简单，把费用网络先拿出来。借费用最短路作 为可行流的可增广链，从而在保证流量的同时，又保证 费用最低。看下图：,上图为0流图，边上的括号内为,在此可增广链上，取容量最小的值min8,5,7=5, 调 整量为5。调整后图为,此时，网络流量为 =510，此流的费用为：,返回到费用网络中，继续找最短路，进而继续调整。在下 面流量的调整中，注意到图（c)有些边的流量已饱和，只能 降低，不能再升，如 。而有些边可降，可升。 如 。