第六章 图与网络分析

1 第六章第六章网络优化网络优化 我们在工农业生产 交通运输和邮电通信等部门中经常看到许多的网络 如公路网 铁路网 河道网 灌溉网 管道网 线路网等等 还有许多问题 表面上看去 和网络无 联系 实则可用网络表示之 如生产计划 资本预算 设备更新 项目排程等问题便是如 此 对网络的研究当然是希望解决管理中的一些优化问题 基本的网络最优化问题有四个 即最短路问题 最小支撑树问题 最大流问题 最小费用流问题 网络优化问题中有许多问题的数学模型实际上都是线性规划问题 但若用线性规划的 方法去求解 就非常麻烦 而根据这些问题的特点 采用网络分析的方法去解决倒是非常 简便有效的 6 1 图与网络的基本概念图与网络的基本概念 从前面所举的各个网络实例 可以看到其中一些共性共性的东西 即每个网络都至少包含 两种类型元素 点和线 例如铁路网中的火车站和铁路 电话网中的电话局与线路等 火车站 火车站 铁路 我们把由点和连接点的线所组成的图形叫做图图 并称这些点为图的顶点顶点或图的点 这 些线叫做图的边边 定义定义 1 图是由表示具体事物的点 顶点 的集合和表示事物之间关 12 n Vv vv 系边的集合所组成 且 E 中元素 ei是由 V 中的无序元素对表示 12 n Ee ee ij v v 即 记 并称这类图为无向图无向图 iij ev v GV E 例 6 个顶点和 8 条边的图 126 Vv vv 128 Ee ee v3 e3 e2 e4 v4 e5 v2 e1 v1 e6 e7 e8 v5 v6 图 1 其中 e1 v1 v2 v2 v1 e7 v5 v2 v2 v5 e2 v3 v2 v2 v3 e6 v4 v5 v5 v4 定义定义 2 1 顶点数和边顶点数和边 图中 V 中元素的个数称为 G 的顶点数 记作 p G GV E E 中元素的个数称为图的边数 记作 q G 2 端点和关连边端点和关连边 若 则称 vi vj 是边 ei的端点 边 ei是点 vi和 vj iij ev vE vv 2 的关连边 3 相邻点和相邻边相邻点和相邻边 同一条边的两个端点称为相邻点 简称为邻点 有公共端点的 两条边称为相邻边 4 多重边与环多重边与环 具有相同端点的边称为多重边 如 e7与 e8 两个端点落在一个顶 点的边称为环 如 e4 5 多重图和简单图多重图和简单图 含有多重边的图称作多重图 如图 1 中的图 无环也无多重边 的图称为简单图 简单图的例子见课本 P184 6 完全图与二分图 完全图与二分图 见课本 P185 7 次次 以 vi 为端点的边的条数称作点 vi 的次 记作 d vi 8 悬挂点与悬挂边悬挂点与悬挂边 次为 1 的点为悬挂点 如 v1 与悬挂点相连的边称为悬挂边 如 e1 9 孤立点孤立点 次为 0 的点 如 v6 10 奇点与偶点奇点与偶点 次为奇数的点称为奇点 如 v2为奇点 因为 d v2 5 次为偶数 的点称为偶点 如 v3为偶点 定理定理 1 图中 所有点的次之和是边数的 2 倍 即 GV E 2 i i vV d vq G 证明证明 因为在计算各点的次时 每一条边都计算了 2 次 于是图 G 中的全部顶点的次 之和是边数的 2 倍 定理定理 2 任一一图中 奇点的个数为偶数 GV E 证明证明 设 V1 V2分别是 G 中奇点和偶点的集合 由定理 1 有 12 2 iii iii vVvVvV d vd vd vq G 因为和是偶数 故必是偶数 由于偶数个奇数才能导致偶数 2 i i vV d v 2 q G 1 i i vV d v 从而奇点的个数必须为偶数 定义定义 3 1 链 在一一个图中 一个由点和边组成的交错序列 GV E iijjkkll v e vv ev 称为 G 中由 vi vl的链链 或称为路路 记为 il v v 2 圈 若在链中 有 vi vl 即始点和终点重合 则称链 为圈 也称 il v v 为闭链闭链 闭路闭路 或环 否则就称为开链开链 3 简单链和初等链 若链 中的边均互不相同 则称链 为简单链 若链 中的点 互不相同 则称链 为初等链 3 今后除非特别交代 否则我们仅讨论初等链 例如 在图 1 中 是一条链 且还是初等链 而链 12233465 v e v e v e v 是圈 211223345211 v e v e v e v e v e v 定义定义 4 1 回路 一条闭的链 2 通路 一条开的初等链 3 简单回路 回路中的边都互不相同 4 初级回路 顶点都不相同的回路 定义定义 5 若一个图 G 的任意两个顶点之间至少有一条通路将它们连接起来 则称 G 为 连通图连通图 否则称为不连通图不连通图 例如 图 1 中的图就是不连通的 因 v1 与 v6 之间没有一条通路将它们连接起来 而 是连通图 定义定义 6 1 子图子图 设是图 若 且是图 则称图 GV E 11 VV EE 11 V E 是 G 的子图 111 GV E 2 支撑子图支撑子图 若是的子图 且 即点相同 则称 G1 111 GV E GV E 1 VV 为 G 的支撑子图 例如 在下图中 图 G0是一个图 G1和 G2都是 G0的子图 且 G2还是 G0的支撑子 图 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e3 v4 4 G1 v1 e1 v2 e2 v3 e6 e4 v5 e5 v4 G2 定义定义 7 设图中 对于任意一条边 若相应地都有一个权值 GV E eE w e 则称 G 为赋权图 称为边 e 的权 例如下图 2 就是一赋权图 w e v2 1 3 5 e1 v1 v2 w e1 1 v1 2 v4 2 v5 4 1 3 v3 图 2 由此可见 赋权图不仅指出各点之间的邻接关系 而且也表示各点之间的数量关系 所以赋权图在图的理论及其应用方面有着重要的地位 以上介绍的图都是无向图 但实际上我们碰到的图都是有向图 即边是有向的 例如 v1 v2 v4 其中v1表示某一水系发源地 v6表示这个水系的入海口 图中的箭头表示个支流的水流方向 v3 v5 v6 水系流向图 3 定义定义 8 设是由 n 个顶点组成的非空集合 是由 m条弧 12 n Vv vv ij Aa 有向的边 组成的非空集合 且有 A 中的元素 aij是 V 中一个有序元素对 vi vj 则称 V 和 A 构成了一个有向图有向图 记作 G V A aij vi vj 表明 vi和 vj分别是弧 aij的起点 尾 和终点 头 称有向的边 ai为弧弧 在图中用带箭头的线表示之 例如 在图 3 中 v1 v2 v1 v3 v2 v5 都是 A 中的元素 A 是弧的集合 类似无向图 也可在有向图中对多重边 环 简单图 链等概念进行定义 只是在无 向图中 链与路 闭链与回路概念一致 而在有向图中 这两个概念却不能混为一谈 概 括地讲 就是 一条路必是一条链 然而在有向图中 一条链未必是一条路 只有在每相邻的两弧的一条路必是一条链 然而在有向图中 一条链未必是一条路 只有在每相邻的两弧的 公共节点是其中一条弧的终点 同时又是另一条弧的始点时 这条链才能叫做一条路 公共节点是其中一条弧的终点 同时又是另一条弧的始点时 这条链才能叫做一条路 5 例如 在图 3 中 v1 v1 v2 v2 v2 v5 v5 v5 v6 v6 是一条链 也是一条路 而 v1 v1 v2 v2 v2 v5 v5 v3 v5 v3 是一条链 但不是一条路 定义定义 9 赋权有向图赋权有向图 若在有向图中 对于任意 都存在权值 GV A ij aA 则称 G 为赋权有向图 称为弧的权简记为 ij w a ij w a ij a ij w 注注 1 权可以表示距离 费用和时间等 注注 2 赋权图被广泛用于解决工程技术及科学管理等领域的最优化问题 如下图 4 是 交通运输的公路分布图 v2 3 5 v6 6 5 5 v1 7 4 2 v4 7 1 6 v3 8 v5 4 v7 图 4 定义定义 10 1 网络 赋权图被称为网络 2 有向网络 赋权有向图 3 无向网络 赋权无向图 如何将一个图输入计算机 通常用矩阵来表示一个图并输入计算机进行计算 定义定义 11 一个简单图 G N E 对应着一个 N E 阶矩阵 B b 其中 ik b ik 1 i 0 k 当点与边关联 否则 称 B 为 G 的关联矩阵关联矩阵 下图 5 的关联矩阵为 4535342523141312 eeeeeeee 5 4 3 2 1 11010000 10100100 01101010 00011001 00000111 12 3 6 图 5 一个简单有向图有向图 G N A 也对应着一个 N A 阶矩阵 B b 其中 ik b ik 否则 为头以点当弧 为尾以点当弧 0 a 1 a 1 i i ik ik B 称为 G 的关联矩阵 关联矩阵 图 6 的关联矩阵为 2 1 4 3 图图 6 43322423211312 aaaaaaa 4 3 2 1 1010000 1101010 0111101 0000111 一个简单图 G N E 还对应着一个 N N 阶矩阵 A 其中a ij a ij 否则 邻接和点当点 0 1ji A 称为 G 的邻接矩阵邻接矩阵 图 5 的邻接矩阵为 54321 5 4 3 2 1 01110 10101 11011 10101 01110 45 7 一个简单有向图 G N A 还对应着一个 N N 阶矩阵 A 其中a ij a ij 否则 连向当有弧从 0 i 1j 称 A 为 G 的邻接矩阵邻接矩阵 图 6 图的邻接矩阵为 4321 4 3 2 1 0100 0010 1101 0110 定义定义 12 边权矩阵 边权矩阵 1 对于赋权有向图 可定义一个 3 m 的矩阵 E 第一 第二行分别存放 边的起点和终点 比如 若第 i 条边 ei 的起点和终点分别为 vj vk 则 E 1 i j E 2 i k 第三行则存放各条边上的权 2 对于赋权无向图 也可定义一个 3 m 的矩阵 E 第一 第二行分别存放两个端点 这两个端点中随便哪个放在第一行均可 比如 若第 i 条边 ei 的端点分别为 vj vk 则 E 1 i j E 2 i k 或 E 1 i k E 2 i j 第三行则存放各条边上的权 定义定义 13 带权邻接矩阵带权邻接矩阵 以表示网络 G 中从顶点 vi到 vj的弧的权 无权图只考虑 vi与 vj之 ij w 间的边的权 当 vi到 vj无弧或边时 则矩阵 W 称为图 G 的带权邻接带权邻接 ij w ij w 矩阵 矩阵 如图 4 中的带权邻接矩阵为 0547infinfinf inf0inf653inf infinf028infinf infinfinf075inf infinfinfinf0inf4 infinfinfinf106 infinfinfinfinfinf0 W 8 6 2 树及最小树问题树及最小树问题 树是图论中的一个重要概念 由于树的模型简单而实用 它在企业管理 线路设计等 方面都有着重要的应用 6 2 1 树及树的性质树及树的性质 例 1 某企业的组织结构如下图 1 所示 生产计划科 设计组 技术科 工艺组 行政办公室 供销科 财务科 行政科 厂长 锻压工段 一车间 制造工段 二车间 生产办公室 三车间 四车间 五车间 图 1 若用图表示 则可见图 2 它是一个呈树枝形状的图 树 的名字由此而来 图 2 9 定义定义 10 一个无回路 圈 的连通无向图称为树树 树的性质 树的性质 1 树必连通 但无回路 圈 2 n 个顶点的树必有 n 1 条边 3 树中任意两点间恰有一条初等链 点不相同的链 4 树连通 但去掉一条边 必变为不连通 5 树无回路 圈 但不相邻顶点连一条 恰得一回路 卷 6 2 2 支撑树与最小树支撑树与最小树 定义定义 11 设图是图的支撑子图 若 G1是一棵树 11 GV E GV E 1 EE 记 则称 T 是 G 的一棵支撑树 1 TV E 例如 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e6 e3 v5 v4 0 G 则是 G0的一棵支撑树 0 G 定理定理 图有支撑树图是连通的 G G 证明 是显然的 这可由树的定义与性质即得 下证 设是一连通图 若 G 无圈 则它已是树 它也是它自身的支撑树 若 G 有圈 则G 任取一圈 去其一边 便得到 G 的一支撑子图 G1 若 G1是树 则它就是 G 的支撑树 否 则 在 G1中任取一圈 去其一边 又得到 G 的一连通的支撑子图 G2 如此继续下去 最 后必可得到一无圈的连通支撑图 即 G 的一棵支撑树 6 2 2 最小支撑树最小支撑树 先看一例 如图 某城市计划将 v1 v2 v7共 7 个点用电话线连接起来 各点间可以架设线 路进行连接的情况如图 1 所示 各线段旁边之数字表示该线段之长 现问应如何选择架设 线路使总的电话线路最短 10 实际上 这就是一个求所给图的最小支撑树问题 我们在前面已知道赋权图的定义 下面给出支撑树的权的定义 v2 4 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 图 1 定义定义 12 设是赋权图的一棵支撑树 称中全部边上权数之 TV E GV E E 和为支撑树 T 的权 记为 即 w T ij ij v vE w Tw 所谓最小支撑树问题最小支撑树问题 就是要求 G 的一棵支撑树 使最小 此时称为 G T w T T 的最小支撑树 简称为最小树 即 min T w Tw T 求最小树的常用方法是 Kruskal 算法和 Prim 算法 Kruskal 算法算法 设给定了一个赋权图 连通的 G Kruskal 于 1956 年证明了按照下述 方法总可以得到 G 的一棵最小支撑树 Step1 开始将 G 的所有各边按权由小到大的次序都排列出来 然后逐边检查 注 对于权相同的边 其先后次序是任意的 Step2 首先留下最短的一条边 然后再检查每一条边 若它不与已留下的边形成圈 就留下来 否则就去掉 Step3 重复 Step2 直到所有被留下来的边形成支撑树时 就终止计算 例 1 求图 1 中的一棵最小支撑树 v2 4 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 图 1 11 解 各边按权由小到大的次序排列如下 用 i j 表示 vi vj 边 2 3 4 5 6 7 4 6 5 7 5 6 2 5 2 4 3 6 3 4 1 3 1 2 首先留下 2 3 然后留下 4 5 6 7 接着在 4 6 和 5 7 之间任意 留下一边 比如留下 5 7 这时 4 6 就应去掉 因为它与 4 5 5 7 6 7 形成圈 5 6 不能留 因为它与 5 7 6 7 形成圈 接下来应留下 2 5 去掉 2 4 3 6 3 4 1 2 留下 1 3 至此最小 生成树已形成 如图 2 v2 4 v5 5 2 3 v1 1 v4 v7 7 2 v3 v6 图 2 其权为 1 2 2 3 4 7 19 注注 在一般情况下 若 G 含有 n 个点 其支撑树含有 n 1 条边 因此 若用上述方法 找到了 n 1 条边且不形成圈 则也找到了最小支撑树 Prim 算法算法 该算法于 1957 年由 Prim 提出 它不要求预先把 G 的边排成一定顺序 开始时 从 G 中取出权最小的一边来 把它 包括端点 看作一棵树 然后把此树逐步扩 大 直到支撑整个 G 为止 每次扩大时 都是先考虑那些与作出的树有边相连的各点 从 中找出权最小的边 然后把此边及其端点加到已作出的树中去 例 2 用 Prim 算法求图 1 的最小支撑树 解 取出权最小的边 2 3 将它看作树 与此树有边相连的各点为 v1 v5 v6 v4 因边 2 5 上的权最小 故把 2 5 加到树中去 此时树由 2 3 2 5 组成 现在与树直接相连的点有 v1 v4 v6 v7 最小权边是 4 5 将之加入 到树中去 现在与树直接相连的点有 v1 v6 v7 最小权边有 2 条 即 4 6 和 5 7 任取其一 比如取 4 6 加入到树中去 最后易知应把 6 7 1 3 加到树中去 此时所得到的树已是 G 的支撑树 如图 3 v2 4 v5 5 2 v1 1 v4 v7 7 3 2 v3 v6 图 3 12 注 注 此树与 Kruskal 算法所得到的支撑树稍有不同 但其权数仍是 19 这就告诉我们 一 个图的最小支撑树可以不止一个 但它们的权相等 练习练习 1 分别用 Prim 算法和 Kruskal 算法求下图 4 所示网络中的最小树 2 分别设计程序来求下图 4 所示网络中的最小树 1 7 6 3 4 8 5 2 图图 4 Prim 算法 算法 先输入加权图的带权邻接矩阵 5 5 a i j 此图中 5 5 0 1 7 3 inf 1 0 6 inf 4 7 6 0 8 5 3 inf 8 0 2 inf 4 5 2 0 a i j 1 建立处始候选边表 T 2 从候选边中选取最短边 u v TTu v 3 调整侯选边集 4 重复 2 3 直到 T 含有 n 1 条边 Matlab 程序 a 0 1 7 3 inf 1 0 6 inf 4 7 6 0 8 5 3 inf 8 0 2 inf 4 5 2 0 T c 0 v 1 n 5 sb 2 n for j 2 n b 1 j 1 1 b 2 j 1 j b 3 j 1 a 1 j end while size T 2 n 1 minimize i min b 3 T size T 2 1 b i c c b 3 i 1 4 2 5 3 13 v b 2 i temp find sb b 2 i sb temp b i for j 1 length sb d a v b 2 j if d T c T 1 1 4 5 2 4 5 3 1 3 2 5 c 11 故上图的最小生成树的边集合为 1 2 1 4 4 5 5 3 总的费用为 11 Kruskal 算法 输入加权连通图 G 的边权矩阵 顶点数为 n 3 m b i j 本图的边权矩阵为 3 1 1 1 2 2 3 3 4 2 3 4 3 5 4 5 5 1 7 3 6 4 8 5 2 m b i j 1 整理边权矩阵 将按第三行由小到大的次序重新排列 得到新的边权矩阵 3 m b i j 3 m b i j 2 初始化 0 0 0 jTcki t ii 对所有 3 更新 Tt i c 1 1 2 4jjt Bjt Bj 若则转 1 2 1t Bjt BjBB 否则 若 则TT j 2 j cc B 3 j kk 1 min t i 对所有i 若t i m ax t B 1 j t B 2 j 则t B 1 j t B 2 j 4 若1 3 knjnTc 或则终止 输出 否则返回 14 Matlab 程序如下 b 1 1 1 2 2 3 3 4 2 3 4 3 5 4 5 5 1 7 3 6 4 8 5 2 B i sortrows b 3 B B m size b 2 n 5 t 1 n k 0 T c 0 for i 1 m if t B 1 i t B 2 i k k 1 T k 1 2 B 1 2 i c c B 3 i tmin min t B 1 i t B 2 i tmin min t B 1 i t B 2 i tmax max t B 1 i t B 2 i for j 1 n if t j tmax t j tmin end end end if k n 1 break end end 运行结果如下 T c T 1 2 4 5 1 4 3 5 c 11 故上图的最小生成树的边集合为故上图的最小生成树的边集合为 1 2 1 4 4 5 5 3 总的费用为 总的费用为 11 6 3 最短路问题最短路问题 最短路问题是网络分析中一个基本问题 它不仅可以直接应用于解决生产实际的许多 问题 如管道铺设 线路安排 厂区布局等 而且经常被作为一个基本工具 用于解决其 它优化问题 定义定义 1313 给定一个赋权图 记 D 中每一条弧上的权为 DV A ijij av v 又给定 D 中的一个起点 vs和一个终点 vt 并设 P 是 D 中从 vs到 vt的一条路 ijij w aw 15 则定义路 P 的权是 P 中所有弧的权之和 记为 即 w P ij ij v vP w Pw 又若是图 D 中从 vs到 vt的一条路 且满足 对 D 中所有从 vs到 vt的路 P 有 P min st P w Pw PPvv 为到的路 则称为从 vs到 vt的最短路最短路 为从 vs到 vt的最短距离最短距离 P w P 在一个图中 求从 vs到 vt的最短路和最短距离的问题就称为最短路问题最短路问题 DV A 为简便起见 约定 从 v1到 vj的最短路和及其长度 就说成是 vj的最短路和及其 路长 注 最短路问题中的权还可以表示时间 费用等 这样最短路就是最节省时间 最节 约费用的方案 应用实例应用实例 问题 问题 某公司有一台已使用 1 年的生产设备 每年年底 公司要考虑下一年度是购买新设备 还是继续使用这台旧设备 若购买新设备 就要支出一笔购置费 若继续使用旧设备 则 要支付维修费用 而且随着使用年限的延长而增长 已知这种设备每年年初的购置价格见 下表 1 不同使用年限的维修费用见表 2 而第一年开始时使用的有 1 年役龄的老设备其净 值为 8 试制定一个 5 年内设备的使用或更新计划 使 5 年内设备的使用维修费和设备购 置费的总支出最小 表 1 年份2345 年初价格11121213 表 2 使用年限0 11 22 33 44 55 6 年维修费用23581218 解解 用点 vi表示 某 i 年初购买一台新设备的情况 但 v1的情况除外 v1只表示第只表示第 1 年初年初 开始使用役龄为开始使用役龄为 1 的老设备的情况的老设备的情况 v6可理解为第五年年底 从 vi到 vi 1 v6各画 1 条 弧 弧 vi vj 表示在第 i 年初购买的设备一直使用到某 j 年年初 即第 j 1 年年底 弧 vi vj 的权 wij表示在第 i 年初购买的设备一直使用到某 j 年年初的支出费用 每条弧的权可按表 1 和表 2 已给的数据计算出来 例如 w25 是第二年年初购买 1 台 新设备的费用 11 加上一直使用到第 5 年年初的维修费 2 3 5 10 共 21 而 w13是第一 年年初使用已有 1 年役龄的老设备的净值 8 加上一直使用到第 3 年年初的维修费 3 5 8 共计 16 其中维修费的使用年限从 1 2 开始计算 同理 w12 8 3 11 w14 8 3 5 8 24 w15 8 3 5 8 12 36 w23 11 2 13 w24 11 2 3 16 w26 11 2 3 5 8 29 16 w34 12 2 14 w35 12 2 3 17 w36 12 2 3 5 22 w45 12 2 14 w46 12 2 3 17 w56 13 3 15 可以将所有弧的权 wij计算出来 计算结果见表 3 表 3 wij vj vi v1v2v3v4v5v6 v101116243654 v2inf013162129 v3infinf0141722 v4infinfinf01417 v5infinfinfinf015 v6infinfinfinfinf0 最短路的数学模型见下图 54 36 22 24 17 16 v1 11 13 14 14 15 v2 v3 v4 v5 v6 16 17 21 29 图 3 用 Dijkstra 算法计算后可得最短路为 v1 v3 v6 即老设备使用 2 年后 在第三年年 初更新设备一直使用到第五年年底 其总费用为 38 G1 0 11 16 24 36 54 inf 0 13 16 21 29 inf inf 0 14 17 22 inf inf inf 0 14 17 inf inf inf inf 0 15 G G1 inf inf inf inf inf inf dijkstra path 1 2 0 0 0 11 1 3 0 0 0 16 17 1 4 0 0 0 24 1 2 5 0 0 32 1 3 6 0 0 38 6 3 1 Dijkstra 算法算法 Dijkstra 算法简称为 D 氏算法 它只适合于所有的有向图或无向图的情形 现0 ij w 假设有向图满足此条件 DV A D 氏算法是一种标号法标号法 也就是对有关的点逐个进行标号的方法 一个点 vj的标号由 实数 j和非负整数 j组成 记为 j j 其中 j就是 v1到 vj的最短路之长度 而 j则是指明 vj的标号是从哪一点得来的 例如 若 vj的标号是 2 3 则说明从 v1到 vj 的最短路之长度是 2 而 vj的标号是从 v3得来的 基本思路 D 氏算法是一种迭代法 首先给 v1标号 方法见后 然后再逐步扩大已 标号点的范围 一旦当 vt获得标号时 则问题便已解决 然后再用 反向追迹 的办法 求出 vt之最短路 由于每一步迭代过程中都将使一个新点获得标号 故只需有限轮便可完成整个计算 下面通过例子来说明 D 氏算法 例例 1 有一批货物从 v1运到 v8 这两点间的交通路线如下图 1 所示 求从 v1到 v8的最 短路径和最短路程 v2 6 3 9 v5 8 4 2 1 v1 0 0 2 v3 2 1 5 v6 7 3 8 v8 13 7 11 2 1 4 2 v4 8 6 12 v7 11 6 图 1 解 将图 D 的全部点分成两部分 已标号点为一部分 记为 未标号的点为另一X 部分 记为 令X ijij O Xv vvX vX 它表示起点属于而终点属于的弧的全体 XX Step0 给定 v1标号 0 0 因为显然 1 0 又规定 1 0 于是 v1成为初始标号 18 点 即有 X 0 v1 并将 v1的标号写在该点的下面或旁边 Step1 O X 0 v1 v2 v1 v3 v1 v4 为了获得新的标号点 在一般情 况下 需要对 O X 中的每一弧 vi vj 计算一个数 ij ij a i wij 其中 ai 是点 v1到 vi 的最短路长 wij 是弧 vi vj 的长度 在上例中 我们有 12 a 1 w12 0 8 8 13 a 1 w13 0 2 2 14 a 1 w14 0 11 11 为便于从图上直接看到计算结果 可将每个 ij 写在弧 vi vj 上靠近 vj处 并加上方框 见图 1 因 min 12 13 14 13 2 故知从 v1到 v3最短路长是 2 即有 a3 2 又 v3是从 v1得到标号的 故 3 1 从而 v3获得标号 2 1 于是已标号点为 X 1 v1 v3 Step2 O X 1 v1 v2 v1 v4 v3 v2 v3 v6 因 12 8 14 11 32 a 3 w32 2 4 6 36 a 3 w36 2 5 7 故 min 12 14 32 36 32 6 故知从 v1到 v2最短路长是 6 即有 a 2 6 又点 v2是从点 v3得到标号的 故 2 3 从而 v2获得标号 6 3 于是已标号点为 X 2 v1 v3 v2 Step3 O X 2 v1 v4 v3 v6 v2 v5 因 14 11 36 7 25 a 2 w25 6 9 15 故 min 14 25 36 36 7 从而知从 v1到 v6最短路长是 7 即有 a 6 7 又点 v6是 从点 v3得到标号的 故 6 3 从而 v6获得标号 7 3 于是 X 3 v1 v3 v2 v6 Step4 O X 3 v1 v4 v2 v5 v6 v4 v6 v7 v6 v8 因 14 11 25 15 64 a 6 w64 7 1 8 67 a 6 w67 7 4 11 68 a 6 w68 7 8 15 故 min 14 25 64 67 68 64 8 从而点 v4的标号是 8 6 a 4 4 于 是 X 4 v1 v3 v2 v6 v4 Step5 O X 4 v2 v5 v6 v8 v6 v7 v4 v7 因 25 15 68 15 67 11 47 a 4 w47 8 12 20 故 min 25 68 67 47 67 11 从而点 v7的标号是 11 6 a 7 7 于是 X 5 v1 v3 v2 v6 v4 v7 Step6 O X 5 v2 v5 v6 v8 v7 v8 因 25 15 68 15 78 a 7 w78 11 2 13 故 min 25 68 78 78 13 从而点 v8的标号是 13 7 a 8 8 于是从 v1到 v8 最短路长是 13 而最短路径可采用反向追迹法反向追迹法得到 v1 v3 v6 v7 v8 注 注 若想求出 v1到所有其它各点的最短路 则继续上述过程 直到每一个点都得到标 号为止 现把 D 氏算法小结一下 Step1 给点 v1标号 0 0 得 X 0 v1 Step2 一般地 设已有 X k 若 vt X k 说明 vt已标号 便可找出 vt的最短路 计 算终止 否则转 Step3 Step3 若 O X k 则计算终止 说明不存在从 v1到 vt的路 反之 对 O X k 中 19 的每一条弧 vi vj 计算一个数 ij a i wij 设 rs a r wrs 若有几个 ij同时达到最小值 则可任取一为 rs 于是得到 vs的标号为 rs r 将新 标号点 vs加入到 X k 中 令 k k 1 转 Step2 利用 D 氏算法 完成下列练习 如图 2 所示的是某地区交通运输示意图 试问 从 v1出发 经过哪一条路线到达 v8才 能使总行程最短 7 3 4 2 6 1 5 2 9 1 3 6 1 5 5 图 2 提示 最短路径是 v1 v2 v3 v6 v7 v8 最短路长是 12 6 3 2 Dijkstra 算法的理论证明算法的理论证明 为了说明 D 氏方法的正确性 还需要以下结论 定理定理 1 若点 vj得到了标号 j j 则 j就是 vj的最短路长 且从 vj开始 用反向追反向追 迹法迹法必可求得 vj的最短路 2 若在计算结束时 点 vj没有得到标号 则不存在从 v1到 vj的有向路 6 3 3 最短链问题最短链问题 类似于有向图中的最短路问题 在无向图中有所谓的最短链问题 设图的每一边 vi vj e 上有一权 w e wij 0 定义 G 中一条链的 GV E 权为 ij ij ev v ww ew 所谓最短链问题最短链问题 就是要在 G 中求出一条从给定的一点 v1到任意一点 vt的链 使 是所有 v1 vt 链中权的最小者 此时称是 v1到 vt的最短链 最短链问题也是用 D 氏算法来求解 不过在标号过程中不是考察弧集 而是考察边集 每一轮计算中仍以和分别表示 V 中已标号点集和未标号点集 并以XX ijij Xv vvX vX v1 v2 v3 v4 v5 v6 v7 v8 20 它表示图 G 中一个端点属于而 而另一个端点属于的边集合 下面通过例题来介绍XX 该方法 例例 2 求图 2 中 v1运到 v8的最短链 v2 9 v5 8 4 2 1 v1 2 v3 5 v6 8 v8 11 2 1 4 2 v4 12 v7 图 2 Step0 给点 v1标号 0 0 1 1 得 X 0 v1 Step1 X 0 v1 v2 v1 v3 v1 v4 12 a 1 w12 0 8 8 13 a 1 w13 0 2 2 14 a 1 w14 0 11 11 因 min 12 13 14 13 2 故从 v1到 v3的最短路长是 2 v3的标号为 3 3 2 1 于是 X 1 v1 v3 Step2 X 1 v1 v2 v1 v4 v3 v2 v3 v6 v3 v4 12 8 14 11 32 a 3 w32 2 4 6 36 a 3 w36 2 5 7 34 a 3 w34 2 2 4 因 min 12 14 32 36 34 34 4 故知从 v1到 v4的最短路长是 4 v4获得标 号 4 3 4 4 于是 X 2 v1 v3 v4 Step3 X 2 v1 v2 v3 v2 v3 v6 v4 v6 v4 v7 12 8 32 6 36 7 46 a 4 w46 4 1 5 47 a 4 w47 4 12 16 因 min 12 32 36 46 47 46 5 故 v6获得标号 5 4 6 6 于是 X 3 v1 v3 v4 v6 Step4 X 3 v1 v2 v3 v2 v4 v7 v6 v5 v6 v8 v6 v7 12 8 32 6 47 16 65 a 6 w65 7 68 a 6 w68 13 67 a 6 w67 9 因 min 12 32 47 65 68 67 32 6 故 v2获得标号 6 3 2 2 于是 X 4 v1 v3 v4 v6 v2 Step5 X 4 v4 v7 v6 v5 v6 v8 v6 v7 v2 v5 47 16 65 7 68 13 67 9 25 a 2 w25 6 9 14 因 min 47 65 68 67 25 65 7 故 v5获得标号 7 6 5 5 于是 X 5 v1 v3 v4 v6 v2 v5 Step6 X 5 v6 v8 v6 v7 v5 v8 68 13 67 9 58 a 5 w58 7 1 8 因 min 68 67 58 58 8 故 v8获得标号 8 5 8 8 由此可知 从 v1运到 v8的最短链长是 8 最短链是 v1 v3 v4 v6 v5 v8 6 3 4 Dijkstra 算法的算法的 Matlab 编程编程 21 Dijkstra 算法 算法 求 G 中从顶点 v0 到其余顶点的最短路 在用 Matlab 编程时 引入记号 S 它表示具有永久标号的顶点集 且对于每个顶点 我们定义两个标记 l v z v 其中 l v z v 算法的过程就是 6 3 5 Floyd 算法算法 前面所介绍的 D 氏算法要求所有的权 wij 0 若有某个 wij 0 则 D 氏算法失效 例 如 如下图 3 所示 要求 v1 到 v2 的最短路 如果用 D 氏算法求 则 w 2 但实际 上 w 0 v3 4 4 v1 2 v2 图 3 因此当有负权时 需另找其他方法 现介绍允许有负权时求最短路问题的 Floyd 算法 首先注意到 若一个有向图 D 中存在权为负数的回路 负回路 则在该图中从一点 走向另一点时 若遇上负回路的一个点 便可在这个回路多绕几次 使得总路长不断下降 这样两点间的长度就没有下界 如下图 4 中 回路 v2 v3 v4 v2 的长为 2 故从 v1 到 v5 的最短路的长度无下界 因此 以下假设假设 D 中不存在负回路中不存在负回路 在此假设下 从一点到另 一点的最短路总可以取成初等路 v4 5 v3 2 1 3 v1 1 v2 2 v5 图 4 设给定有向图 D V E 及 E 上的权函数 w e 若 V 中的两点 vi和 vj之间无弧相连 则令 w vi vj 这样便可认为任何两点之间都有弧相连了 为方便起见 以 wj 表示从 vi到 vj 的最短路的权 记 w vi vj wij 又设 V 的点数为 n 易知 wj j 1 2 n 必须满足以下方程 1 min 1 2 i jiij vV wwwjn 并规定 0 ii wi 方程 1 可用迭代法来求解 步骤如下 22 开始 令 一般地 设已有各个 则 0 1 1 2 jj wwjn 1 k j w 1 min i kk jiij vV www 1 2 jn 当迭代过程进行到某一步 发现有 1 1 2 kk jj wwj jn 则计算停止 此时即是 v1到 vj 的最短路的权 k j w 理论上可以证明 上述算法最多经过上述算法最多经过 n 1 1 次迭代必定收敛 即或者次迭代必定收敛 即或者 01kkn 使得使得 或者在已算出的序列 或者在已算出的序列中至少存在某个中至少存在某个 j 使得 使得 1 1 2 kk jj wwjn 1 n j w 在前一种情况下 我们已求出从 在前一种情况下 我们已求出从 v1到到 vj 的最短路的权 在后一种情况下 的最短路的权 在后一种情况下 1 2 nn jj ww 说明图说明图 D 中有负回路 中有负回路 下面通过具体的例子来说明 Floyd 算法的应用 例 求下图中从 v1到各点的最短路 v1 5 v4 3 3 2 2 2 v3 1 4 4 7 v2 2 v5 3 解解 显然图中无负回路 权矩阵为 1 2 3 4 5 023 202 240 5301 3740 ij v v Wwv v v 1 v 2 v 3 v 4 v 5 v 23 Step0 令 0 1 1 2 3 4 5 jj wwj Step1 由知 1 0 min 1 2 3 4 5 i jiij vV wwwi j 1 0 1111 min 00 22 3 2 0www 1 0 2332 min 02 20 3 4 1www 或 1 0 3113 min 03 23 30 3www 0 333 ww 1 4 w 1 0 5225 min 0 22 3 1 0 0www Step2 由知 2 1 min 1 2 3 4 5 i jiij vV wwwi j 2 1 1111 min 00 12 3 2 0www 或 2 1 2332 min 02 1 0 3 4 03 1www 1 222 ww 2 1 3113 3www 2 1 4554 4www 2 1 5225 3www Step3 由知 3 2 min 1 2 3 4 5 i jiij vV wwwi j 3 1 0w 3 2 2332 1www 3 2 3113 3www 3 2 4554 1www 3 2 5225 3www Step4 由知 4 3 min 1 2 3 4 5 i jiij vV wwwi j 4 1 0w 4 3 2332 1www 4 3 3113 3www 4 3 4554 1www 4 3 5225 3www 由于 故停止计算 从而得到 v1到各点 v1 v2 v3 v4 v5的最 3 4 1 2 3 4 5 jj wwj 短路的权分别是 0 1 3 1 3 计算结果见表 其中表的最左边部分是初始数据 中间部分是各次迭代的计算结果 最右边的一列数据就是从 v1到各点 v1 v2 v3 v4 v5的最短 路的权 24 0 j w 1 j w 2 j w 3 j w 4 j w 00000 2 1 2 1 3 2 1 3 2 1 3 2 1 3 2 3 1 3 3 1 3 3 1 3 3 1 3 3 1 3 infinf4 5 4 1 5 4 5 4 inf0 2 5 3 2 5 3 2 5 3 2 5 为求具体的最短路线 可以在求出 wj后 采用反向追踪的方法寻找 如已知 wj后 找 vj后 使 wi wij wj 记下弧 vi vj 再对 wi 又找一点 vs 使 ws wsi wi 又记下弧 vs vi 如此继续下去 直至达到 v1为止 最后便得 v1到 vj的最短路为 v1 vs vi vj 本例 中 v1到 v5的最短路为 v1 v3 v2 v5 6 3 6 Floyd 算法的算法的 Matlab 编程编程 在不存在负回路不存在负回路的假定下 求任意两点之间的最短路 FloydFloyd 算法求最短路线及距离的算法求最短路线及距离的 MATLABMATLAB 源程序源程序 借助 MATLAB 软件 用 Floyd 算法求取网络优化中最短路线及距离 即求带权邻接矩阵 的加权图中的最短路径及其长度 加权有向图的存储结构采用带权邻接矩阵 网络图分为有向图和无向图 对于无向图 可以看成是有向图两点之间 n nAa i j 的循环 即把变为 其中 ij ij a i ja j i MATLAB 程序 存储为 floyd1 m 文件 function D path floyd1 a a 是带权邻接矩阵 当 i 与 j 不相同时 若 i 与 j 相连就取其权 否则 当 i 与 j 相同时 元素取 0 n size a 1 设置 D 和 path 的初值 D a path zeros n n for i 1 n for j 1 n if D i j inf path i j j j 是 i 的后继点 end end end 做 n 次迭代 每次迭代均更新 D i j 和 path i j for k 1 n 25 for i 1 n for j 1 n if D i k D k j 0 故 v5可以得到标号 2 此时 v3 v4 v5都是已标号而未检查的点 任取其一 比如 v5进行检查 发现 v6可以得到标号 5 由于收点 v6已获得标号 故应该立即用反向追迹法找到增广链 因 v6的标号是 5 故增广链的最后一段是 v5 v5 v6 v6 因 v5的标号是 2 故往前一 段的弧是 v2 v5 v2 v5 因 v2的标号是 1 故再往前一段的弧是 v1 v1 v2 v2 于是得到增广链为 v1 v1 v2 v2 v5 v2 v5 v5 v6 v6 其中 v1 v2 和 v5 v6 是前向弧 v5 v2 是后向弧 此时 1 min 124 6 1 5 2 min 1 1 从而 12 min 1 调整后的新流如下图 5 其值为 8 v2 5 v4 12 3 7 15 v1 6 4 v6 6 6 v3 5 v5 图 5 现对图 5 中所示的流再用一次标号法 首先给 v1以标号 0 对 v1进行检查 发现 v2 v3都可以得到标号 1 任取其一 比如 v2进行检查 发现 v4可以得到标号 2 检查 v4时 发现 v6可以得到标号 4 用反向追迹法找到增广链为 v1 v1 v2 v2 v2 v4 v4 v4 v6 v6 此时 1 min 125 53 156 2 从而 1 min 2 调整后的新流如下图 6 其值为 10 v2 5 v4 12 3 7 15 v1 6 4 v6 6 6 v3 5 v5 33 图 6 注意注意 弧 v2 v4 已饱和 不能再调整 对图 6 中所示的流再用一次标号法 首先给 v1以标号 0 对 v1进行检查 发现 v2 v3都可以得到标号 1 任取其一 比如 v3进行检查 发现 v4 v5可分别获得标号 3 3 检查 v4时 发现 v6可以得到标号 4 用反向追迹法可找到增广 链为 v1 v1 v3 v3 v3 v4 v4 v4 v6 v6 此时 1 min 63 76 158 1 从而 1 min 1 调整后的新流如下图 7 其值为 11 v2 5 v4 12 3 7 15 v1 6 4 v6 6 6 v3 5 v5 图