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

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

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

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

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

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

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

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

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

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

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

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

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

表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

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

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

① ② ⑴ ⑵ 给 划成彩线。 ⑶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注意到：

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

只有一个新增元素

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一次标号。 调整

再调整。 第二次标号。

第三次标号。

调整。

第四次标号。

调整

第五次标号。

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

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

例/习题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

解：设 ， 分别表示每项运输任务的出发日期及 完成日期（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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

③ ② ① ③ ② ①

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

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

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

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

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

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

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

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

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

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

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