∞
• 例5.2 在图5.14中，试求：
（1）各点到v6的最短路； （2）v1到各点的最短路。
图5.14 例5.2图
• 我们根据题意可以写出上述网络的距离 矩阵为
0 5 2 ∞ ∞ ∞
∞ 0 4 3 ∞ ∞
∞ 4 0 ∞ 3 ∞ W ∞ 2 5 0 5 ∞
∞ ∞ 4 2 0 4
∞ ∞ ∞ 2
• 图论（Graph Theory）已经成为运筹学 的一个重要分支，是建立和处理离散数学 模型的一个重要工具。
• 人们对图和网络的研究可以追溯到18世 纪50年代。
• 1736年，“哥尼斯堡七桥问题”被欧拉 （E Euler）用一篇题为“依据几何位置的 解题方法”的论文解决。
• 在随后的200多年里，人们也一直致力于图 和网络的研究，特别是在20世纪中期以后， 随着离散数学和计算机技术的发展，图和网 络的研究更是得到了飞速发展。
• 以后每次都检查刚得到固定标号那点， 对其所有关联边的终点修改临时标号，然 后从一切临时标号中选出最小的把它改为 固定标号，同时选出相应的弧，具体过程 如图5.8～图5.13所示。
• 从图5.13可以看出，从点s到点t的最短路 径为s→②→⑤→⑥→t，最短路长度为28。
图5.9 例5.1（3）图
min{T(vj), P(vi)＋wij} = >T(vj)
（3）从一切vj∈T中选取并令 min{T(vj)} = T(vr) = >P(vr)
选取相应的弧（vi, vr）。
• 再令S∪｛v r｝=>S, T\｛vr｝=>T。
（4）若T =φ，则停止。
• 即P(vj)为vs到vj的最短路径，特别P(vt)即vs 到vt的最短路长，而已选出的弧即给出vs到 各点最短路；否则令vr = >vi，返回步骤 （2）。
1．符号定义和相关规定
• 它们的含义为 P(vj)：从始点vs到vj的最短路长； T(vj)：从始点vs到vj的最短路长上界。
2．狄克斯屈标号法的基本步骤
（1）令S = {vs}为固定标号点集， T = V \{vs}为临时标号点集。
• 可得 P(vs) = 0
T(vj) = ∞ vj∈T
（2）检查点vi，对其一切关联边（vi, vj） 的终点vj∈T计算并令
1．网络的距离矩阵
• 设一个网络N中有n个节点，其中任意两 点vi与vj之间都有一条边（vi, vj），其权数 wij＞−∞。
• 若vi与vj不相邻，则虚设一条边（vi, vj） 并令其权数为wij=∞。
• 如此可以定义一个矩阵：
W=(wij)n×n （5-1） 称为网络N的直接距离矩阵，简称距离矩阵。
图5.5 链
5．连通图
• 在一个图中，若任意两点之间至少存在 一条链，则称该图为连通图，否则就是不 连通图。
图5.6 不连通图
5.2 最短路径问题
• 最短路径问题通常分为如下两类。
（1）从始点到其他各点的最短路径。 （2）所有任意两点间的最短路径。
• 本节主要介绍求最短路径的两种算法： 狄克斯屈标号法和距离矩阵摹乘法。
• 目前，网络分析的理论已经在工程设计、 管理科学、交通规划、通信网规划等众多领 域得到广泛的应用，并取得了丰富的成果。
5.1
有向图
5.2
最短路径问题
5.3
网络最大流问题
5.4
网络规划的应用案例
5.5 网络规划问题的Excel处理
5.1 有向图
• 5.1所示为某连锁超市7个门店之间的道路 交通示意图，①、②、③、④、⑤、⑥、 ⑦分别表示7个门店，各门店之间的连线称 为道路。
• 选出最小标号：min｛T(2)，T(3)，T(4)｝=7。
• 将T(4)改为P(4) = 7，其弧为（s, ④）。
• 在图5.7中④的数字7加上方框，在图5.7中 ②旁写上数字9，在图5.7中③旁写上数字13。
• 如图5.8所示，图中带箭头的线即为所选弧。
图5.7 例5.1（1）图
图5.8 例5.1（2）图
（1）节点。
图5.1 某超市7个门店的道路交通示意图
（2）边。 （3）图。
（4）网络。
图5.2 网络示意图
5.1.2 无向图与有向图
1．无向图 2．有向图
图5.3 有向图
3．混合图
图5.4 混合图
5.1.3 端点，关联边，相邻，次，链
1．端点和关联边 2．相邻 3．次，奇点，偶点 4．链
图5.10 例5.1（4）图
图5.11 例5.1（5）图
图5.12 例5.1（6）图
图5.13 例5.1（7）图
5.2.2 距离矩阵摹乘法
• 距离矩阵摹乘法是基于这样的事实：如 果节点vs到节点vj的最短路径总是沿着某一 特定路径先到达节点vi然后再沿边（vi，vj） 到达节点vj，则这一特定路径肯定也是节点 vs到节点vi的最短路径。
• 例5.1 求图5.7中始点s到终点t的最短路径 ②、③、④ 修改临时标号：
点②：min｛T(2)，P(1)＋w12｝=min｛∞,0 + 9｝=9T(2) 点③：min｛T(3)，P(1)＋w13｝=min｛∞,0 + 13｝=13T(3) 点④：min｛T(4)，P(1)＋w14｝=min｛∞,0 + 7｝=7T(4)
第5章 图与网络规划
学习目标
了解图论和网络分析中常见的概念和术语。 学会最短路问题的狄克斯屈标号法；最短 路问题的距离矩阵摹乘法；最大流最小截集 问题的福特—福尔克逊标号法；网络的中心 和重心的求法；多端网络问题的转化。
• 在日常生活中，各种各样的网络图随处 可见，如道路交通图、电话网络图、电路 图等。
5.2.1 狄克斯屈标号法
• 该法是狄克斯屈在1959年提出的，适用 于所有权数均为非负（即一切wij≥0）的网 络，能够求出任意一点vs到其他各点的最 短路径，该法为目前求这类网络最短路径 的最好算法。
• 狄克斯屈标号法可用于计算两节点之间 或一个节点到所有节点之间的最短路径。
•是 也 标它从必号的v是的1基到从方本vv法n1的思到，最路v从n短−是始1的路：点最径若开短，（始路则v，1径,（v逐2，v,…步1,因v向,2此v,…n外-可1,,收vv采nn缩）-用1） 从始点到其他各点的最短路径。