第八章 图与网络分析 最短路问题 最短路的应用.

Presentation on theme: "第八章 图与网络分析 最短路问题 最短路的应用."— Presentation transcript:

1 第八章 图与网络分析 最短路问题 最短路的应用

2 第一讲： 最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优 化问题都可以使用这个模型，如设备更新、管道的铺设、
线路的安排、厂区的布局等。 最短路问题的一般提法是：设 为连通图，图中 各边 有权 ( 表示 ， 之间没有边）, 为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即： 最小。

3 最短路算法中1959年由 （狄克斯特洛）提出的 算法被公认为是目前最好的方法，我们称之为 算 法。下面通过例子来说明此法的基本思想。 条件：所有的权数 思路：逐步探寻。

4 标号（0）。画第一个弧。（表明已 标号，或已走出 ）
① 下求 到 的最短路： 1）从 出发，向 走。首先，从 到 的距离为0，给 标号（0）。画第一个弧。（表明已 标号，或已走出 ） 2） 从 出发，只有两条路可走 ，其距离为

5 ① ② 可能最短路为 ① 给 划成粗线。 ② 给 标号（4）。 ③ 划第二个弧。

6 表明走出 后走向 的最短路目前看是 ，最优距离 是4 。
① ② 表明走出 后走向 的最短路目前看是 ，最优距离 是4 。 现已考察完毕第二个圈内的路，或者说，已完成 的标号。

7 ① ② ③ 3）接着往下考察，有三条路可走： 可选择的最短路为 ① 给 划成粗线。 ② 给 标号（6）。 ③ 划第3个弧。

8 ① ② ③ ④ 4）接着往下考察，有四条路可走： 可选择的最短路为 ① 给 划成粗线。 ② 给 标号（8）。 ③ 划第4个弧。

9 ① ② ③ ④ ⑤ 5）接着往下考察，有四条路可走： 可选择的最短路为 ① 给 划成粗线。 ② 给 标号（9）。 ③ 划第5个弧。

10 ① ② ③ ④ ⑤ ⑥ 6）接着往下考察，有四条路可走： 可选择的最短路为 ① 给 划成粗线。 ② 给 标号（13）。 ③ 划第6个弧。

11 7）接着往下考察，有四条路可走： 可选择的最短路为 ① 同时给 划成粗线。 ② 分别给 标号（14）。

12 最后，从 逆寻粗线到 ，得最短路： 长度为15。

13 第二讲：最短路问题的两个应用 最短路问题在图论应用中处于很重要的地位，下面举两个实 际应用的例子。 例12/P264 设备更新问题
某工厂使用一台设备，每年年初工厂要作出决定：继续使 用，购买新的？如果继续使用旧的，要负维修费；若要购买 一套新的，要负购买费。试确定一个5年计划，使总支出最小 若已知设备在各年的购买费，及不同机器役龄时的残值与 维修费，如表8-2所示.

14 表8-2 项目 第1年 第2年 第3年 第4年 第5年 购买费 11 12 13 14 机器役龄 0-1 1-2 2-3 3-4 4-5 维修费 5 6 8 18 残值 4 3 2 1

15 解：把这个问题化为最短路问题。 用点 表示第i年初购进一台新设备，虚设一个点 ，表示第 5年底。 边 表示第i年购进的设备一直使用到第j年初（即第j-1 年底）。

16 边 上的数字表示第i年初购进设备，一直使用到第j年
初所需支付的购买费、维修的全部费用（可由表8-2计算得 到）。 这样设备更新问题就变为：求从 到 的最短路问题.

17 ① ② ⑴ ⑵ 给 划成彩线。 ⑶

18 ① ② ③ ④ 给 划成彩线。 ⑷ 给 划成彩线。

19 ① ② ③ ⑤ ④ ⑸ 给 划成彩线。

20 ① ② ③ ⑤ ④ ⑹ 给 划成彩线。 计算结果：最短路

21 即：在第一年、第三年初各购买一台新设备为最优决策。 这时5年的总费用为49。
① ② ③ ⑤ ④ 最短路路长为49。 即：在第一年、第三年初各购买一台新设备为最优决策。 这时5年的总费用为49。

22 例13 (选址问题P265 ) 已知某地区的交通网络如图8-37所示，
其中点代表居民小区，边代表公路，为小区间公路距离，问区 中心医院应建在哪个小区，可使离医院最远的小区居民就诊时 所走的路程最近？ 解 求中心的问题。 解决方法：先求出 到 其它各点的最短路长 如 再求

23 即为所求。 比如求 ⑴ ⑵ 给 划成彩线。

24 ⑶ 给 标号20。 给 划成彩线。

25 ⑷ 给 标号30。 给 划成彩线。

26 ⑸ 分别给 标号33。 分别给 划成彩线。

27 ⑹ 给 标号63。 给 划成彩线。 其它计算结果见下表：

28 由于 最小，所以医院应建在 ，此时离医院最 远的小区 距离为48。 表 8.1 小区号 0 30 50 63 93 45 60 93
93 63 50 48 由于 最小，所以医院应建在 ，此时离医院最 远的小区 距离为48。

29 三. Floyd （佛洛伊德）算法 这里介绍得Floyd（1962年）可直接求出网络中任意两 点间的最短路。 其中 令网络中的权矩阵为 当 其他 算法基本步骤为： ⑴ 输入权矩阵

30 例14/P266 ⑵ 计算 其中 例如：

31 中不带角标的元素表示从 到 的距离（直接有边），
带角标的元素表示借 为中间点时的最短路长。

32 在放开 的基础上，再放开 中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。

33 注意到： 在放开 点的基础上，再放开 考察最短路。

34 注意到：

35 说明所有点经过 并没有缩短路程。

36 只有一个新增元素

37 表示任意两点间的最短路长及其路径。

38 第二讲 最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输 网络中有人流、车流、货物流、供水系统中有水流，金融
第二讲 最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输 网络中有人流、车流、货物流、供水系统中有水流，金融 系统中有现金流，通信系统中有信息流，等等。 一． 有关概念： 例：下图是输油管道网， 为起点， 为终点， ， ， ， 为中转站，边上的数字表示该管道的最大输油能 力（也称容量），记为 ，问应如何安排各管道输油量， 才能使从到的总输油量最大？

39 ① 分别称 为发点、收点。其余的点称为中间点。
② 每一个边上都给定一个容量的网络称为容量网络，记 的每一个边上都给定一个实际流量 的网络称为给 定了网络一个流。

40 ④容量限制 条件： 对每一边上都有 若 ，称边 是饱和边。 ⑤平衡条件： a) 中间点： 流入量=流出量。 b) 发收点： 发出流量=汇入流量。

41 这种流称为可行流。上图就是一个可行流。使流量达到
最大的流称为最大流 。 ⑥ 可增广链：是指从 到 有一条链，此链上有 ≤ 的现象出现。（非饱和链） 二． 求解最大流： 1） 寻找可增广链： 先给标号 （∆，+∞），其中∆意思是流入的结点，现没 有，纯属一个符号。+∞表示的流出量。因它上面没有结点 来控制它，故设为+∞.

42 b) 接着检查与相邻接的点 ， ， 。 已饱和，流量不
可再增。再检查 ，可调整量为 4-2=2，可提供量+∞，取 调整量

43 给 标号 ，其中 表示 的所调整量2来自 ，且 为正向流（向前流） 。 同理，给 标号 下对已标号点（可望调整点）接着向下检查。 已饱 和。再检查与 相邻接且未标号的点

44 调整量为 给 标号为 d) 检查与 相邻接且未标号的点 ， 。而 对 来讲是流 入，现欲增加流出量，应压缩 的流入量，只要的流入量

45 可令调整量为 给 标号为 表示可控量，反方向流量。

46 f) 下面检查与 相邻接且未标号的点 ，同理，调整量：
给 标号为 g) 最后，给 标号

47 2）调整流量：从 到 所画出的彩线即为可增广链。沿
该可增广链，从 倒推，标“＋”号的在实际流量上加上 该调整量，标“－”符号的在实际流量上减去该调整量。完 成调整过程。

48

49 重新开始标号，寻找可增广链。当标到 时，与 ， 相
邻接的点 ， ， 都不满足标号条件，标号无法继续，且 没有完成标号。此时最大流量即为所求。

50 第三讲：最大流问题的应用 1. 最大匹配问题 ⑴ 二部图（也叫二分图） 图G= (V, E), 若V=X∪Y且X∩Y=ф，使得E中每一条边 的两个端点必有一个属于X，另一个属于Y，则称G为二 部图。记G=（X，Y，E），或G=（X，E，Y）。

51 2．匹配： 对给定的二部图G =（X，Y，E），若有ME，且M中 任意两条边都没有公共端点，则称M为G的一个匹配 （也称对集）。 既满足：一个人只多做一件工作，每件工作只多由一人来 做。即为工作集与工人集之间的一个匹配。

52 3．最大匹配问题：  表示G中所有的匹配集，即  =｛M | M为G的匹配集｝ |M|表示M的边数，若存在 M0 使对任意的M∈，有 则称 M0 是G 的最大匹配。 注：G中最大匹配方案可能不唯一。 饱和点：M中任意边的端点称为（关于M的）饱和点， G中其他顶点称为非饱和点。

53 求最大匹配问题方法很多，以前学过交替链法，下介绍
最大流法。即所谓 2。多端网络问题： 例16/P-274 设有5位待业者，5项工作，他们各自能胜任 工作的情况如图8-47所示，要求设计一个就业方案，使尽 量多的人能就业。 其中 表示工人。 表示工作。

54 二部图中最大匹配问题，可以转化为最大流问题求解。在
二部图中增加两个新点 分别作为发点，收点。并用 有向边把它们与原二部图中顶点相连，令全部边上的容量 均为1。当网络流达到最大时，如果 上的流量为1， 就让 作 工作，此即为最大匹配方案。

55 第一次标号。 调整

56 再调整。 第二次标号。

57 第三次标号。

58 调整。

59 第四次标号。

60 调整

61 第五次标号。

62 标号过程已无法再继续。流量为1的画彩线。

63 工人 分别作 故最多安排四个人工作。

64 例/习题8.21/P-282：现有5批货物，每批只需一条船装 运，要由 ， 所在地域运往 ， ， 地域。至于货物
应用2 例/习题8.21/P-282：现有5批货物，每批只需一条船装 运，要由 ， 所在地域运往 ， ， 地域。至于货物 从 ， 运向 ， ， 三点何处都一样，每批货物出 发日期如表8-5，航船行所需天数如表8-6。船只空载和 重载时航行时间相同。要求制定一个计划，在半个月内用 最少的船只把5批货物运过去。 表8-5（出发日期） 表8-6（航行天数） 地点 5 10 / 12 1，8 地点 2 3 1

65 解：设 ， 分别表示每项运输任务的出发日期及 完成日期（i=1，2，3，4，5）则由表8-5和表8-6 知：
解：设 ， 分别表示每项运输任务的出发日期及 完成日期（i=1，2，3，4，5）则由表8-5和表8-6 知： 任务 路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8

66 要想用较少的船只在1～15天内完成任务，关键是自上一任 务到达的时间加上返回的时间能否赶上下一个任务出发的
路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8 要想用较少的船只在1～15天内完成任务，关键是自上一任 务到达的时间加上返回的时间能否赶上下一个任务出发的 时间。若能，则一只船就能完成两批货物的运输任务。 以下试运行：

67 地点 2 3 1 任务 路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8 表8-6（航行天数） ①7号 ①5号 ③13号
8号回 ③14号回 ⑤10号 ⑤8号 12号回

68 共两只船在13号以前就把5批货物全部运了出去。
任务 路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8 表8-6（航行天数） 地点 2 3 1 ④5号回 共两只船在13号以前就把5批货物全部运了出去。 ②10号 ②13号 ④3号 ④1号 是否最优？一只船可行否？如何解决？

69 作一个二部图，点集｛X｝和｛Y｝都表示这5项任务，两 点间有连线的条件是第i件任务完成后可赶上作第j件任务。
有连线即有匹配，连线越多（匹配数越大）一只船重复使 用次数多，使用船只数就越少。最大的匹配就是用最少的 船。 任务 路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8

70 任务 路线 ① 5 7 ② 10 13 ③ 12 ④ 1 3 ⑤ 8 表8-6（航行天数） 地点 2 3 1

71 此表示共两只船可完成任务： Ⅰ：④→①→② Ⅱ：⑤→③ 解不唯一。

72 第四讲：最小费用最大流 一。带负权的最短路问题： 大家知道， 法求最短路只适应于权 ≥0的情况， 当网络中出现负权时，此法失效，如： 求 到 的最短路。

73 下面通过例子来说明带负权的网络的最短路求法：逐次 逼近法：
① 1．给标号 （0）。画弧。

74 ② ① ① 给 划成彩线。 ② 给 标号（-3）。 ③ 划第二个弧。

75 ③ ② ① ① 给 划成彩线。 ② 给 标号（1）。 ③ 划第三个弧。

76 ④ ③ ② ① ① 给 划成彩线。 ② 给 标号（2）。 ③ 划第四个弧。

77 ④ ⑤ ③ ② ① ① 给 划成彩线。 ④ 划第五个弧。 ② 给 再次标号（0）。 ③去掉 彩线。

78 ④ ⑥ ⑤ ③ ② ① ① 分别给 划成彩线。 ② 分别给 标号（6）。 ③ 划第六个弧。

79 ④ ⑥ ⑤ ③ ② ⑦ ① ① 给 划成彩线。 ② 给 标号（10）。 ③ 划第七个弧。

80 ④ ⑥ ⑤ ③ ② ⑦ ① ① 给 划成彩线。 ② 给 标号（9）。 到达 已经无负权，路程不可能再减少。

81 ④ ⑥ ⑤ ③ ② ⑦ ① 最短路径为： 距离：10。

82 §5 最小费用流的问题 前两节主要讲了两个问题：最短路问题和最大流问题。下 面介绍网络中二者的结合问题：最小费用流的问题。 问题的提出是这样的：在一个关于流的网络中，人们不仅 需要流达到一定的数量，（甚至达到最大，即最大流）而 且每一个流量要有一定的费用，流所走的路线不一样，单 位费用不一样。同样数量的流量，可能走的路线不一样， 总的费用不一样。从而在限定网络流的基础上，让流沿那 些边走，能使总的费用最小（这里的最小费用问题又看成 最短路问题）。

83 特别的，当最大流不惟一时，在所有最大流中求一个流f,使
总费用最低。 用规划语言可以这样描述：若给定容量网络 G=（V，E，C） 除给定每个边 上的容量 外，还给定 流量的费用 ，记为 G=（V，E，C，D） 若给定G的一个可行流 , 在总的流量 （常数）下使

84 求最费用最大流的基本思想是：从零流 开 始，以费用作为边的长度，用求最短路的方法，求出可增 广链，调整流量，使其流量逐步达到要求的数量。 下通过例子来说明。 例：在图8-55所示的网络中，求流量为10的最小费用流。 边上括号内为 。

85 先假设此网络是空架子，即0-流。然后，逐步调整流量
到10，在什么路线上增加流量？在费用最小的路线上调 流量。为简单，把费用网络先拿出来。借费用最短路作 为可行流的可增广链，从而在保证流量的同时，又保证 费用最低。看下图：

86

87 ③ ② ① ③ ② ①

88 上图为0流图，边上的括号内为 在此可增广链上，取容量最小的值min｛8,5,7｝=5, 调 整量为5。调整后图为

89 此时，网络流量为 =5≺10，此流的费用为：

90 返回到费用网络中，继续找最短路，进而继续调整。在下
面流量的调整中，注意到图（c)有些边的流量已饱和，只能 降低，不能再升，如 。而有些边可降，可升。 如 。下次调整为了表达上面的意思，我们在费用流 网络中，可升、可降的边用两个箭头表示，如下图：

91 ② ① 下用逐次逼近法求 到 的费用最短路。 ① 标 （0），画第一个弧。 ② 标 （1），画第二个弧。

92 ④ 标号 （5）。画第四个弧。经检查，已没有修改 的必要。
③ ④ ② ① ③ 分别标 （4）、 （4），画第三个弧。 ④ 标号 （5）。画第四个弧。经检查，已没有修改 的必要。

93 显然，流的调整量 为2。调整后为

94 此时，网络流量为 =7≺10，此流的费用为：

95 在已用过的链上，可增可降的双箭头，只增不降的单箭
头。

96 ③ ② ① 下用逐次逼近发求最短路（可增广链）：

97 显然，流的调整量 为3。调整后为

98 此时，网络流量为 =10，最小费用为：

99