院校资料系统工程ch3PPT学习教案

1、会计学121 图的基本概念一、图、连通图、赋权图1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树第1页/共77页31 图的基本概念概述兰德公司简介概述（1）由来生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以用图与网络的形式进行描述 （2）意义不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广泛应用 （3）应用物理学、控制论、信息论、交通运输、经济管理、计算机科学等 （4）用例项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理布局等 第2页/共77页41 图的基本概念一、图、连通图、赋权图 1. 图图论中的图与几

2、何图形的区别一、图、连通图、赋权图1. 图与以前在数学中学的几何图形不完全相同哥尼斯堡七桥问题：ABCD示意图图论中的图BDCe2e1e6e5e7e4e3A欧拉将此问题归结为一个 “一笔画”问题，并证明了是不可能的，因为图中的每个点都与奇数条边相关联，不可能将这个图不重复地一笔画成，这是古典图论中一个著名问题。 第3页/共77页51 图的基本概念一、图、连通图、赋权图 1. 图图的基本概念图论中的图与几何图形的区别几何图形：强调几何要素（如长度、角度、面积、形状等）的准确性（如桥的准确位置、长度、岛的面积大小 ）两个图在图论中完全相同图论中的图：不关注几何要素的准确性，强调点的数量及点之间关系

3、的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥以及有几座桥） BDCe2e1e6e5e7e4e3AABCD第4页/共77页61 图的基本概念一、图、连通图、赋权图 1. 图图的基本概念（续）图的基本概念顶点：定义3-1：ADBCe2e1e4e3e5e6端点：关联边：相邻点：相邻边：环：通常用点表示具体的或抽象的事物，而用边表示事物之间的某种联系。 第5页/共77页71 图的基本概念一、图、连通图、赋权图 1. 图图的基本概念（续）图的基本概念（续）多重图：多重边：ADBCe2e1e4e3e5e6简单图：图的阶：顶点的度：偶点：奇点：含有多重边的图称为多重图。 无环无多重边的图称为简单

4、图。 图中顶点的个数称为图的阶。以v为端点的边的条数称为点v的度，记作 deg(v)或d(v)度为偶数的点称为偶点。 度为奇数的点称为奇点。 规定环计算两次 第6页/共77页81 图的基本概念一、图、连通图、赋权图 1. 图2. 连通图图的基本概念（续）悬挂点：孤立点：ADBCe2e1e4e3e5e6悬挂边：度为1的点称为悬挂点。 与悬挂点关联的边称为悬挂边。 EF度为零的点称为孤立点。 所谓连通图，即图中任意两点都能通过一系列顺序相连边通达，这一系列顺序相连的边称为链。 第7页/共77页91 图的基本概念一、图、连通图、赋权图 2.联通 图3. 赋权图2. 连通图定义3-3（链、圈）：简单链

5、：所有边不重复的链（即各边互不重复）。 v1v2v3v4v5v6v7即各边顺序相连以下概念也适用于圈初等链：所有点不重复的简单链（即点边均不重复）。 连通图：若图中任意两点之间至少存在一条链，则图称为连通图，否则称为不连通图。 第8页/共77页101 图的基本概念一、图、连通图、赋权图 3. 赋权图二、一笔画问题3. 赋权图定义3-4（赋权图）：在实际问题中，常常遇到每条边对应一个数量指标的情况。例如，若用边表示线路（电线、公路、铁路、管道等），则往往要考虑它们的长度，或相应的运输价格等，这时，我们需为图的各边给出相应的数量指标，并称之为“权”。 相对于非赋权图，赋权图在图论的理论和应用方面有

6、着重要的地位，赋权图中的边不仅表示图中各点之间的关联关系，而且同时表示出了各点之间的数量关系，所以赋权图被广泛应用于各领域的最优化问题。 定义3-5（图的权）：图中各条边权的和称为图的权，记作 GvvijjiwGW，第9页/共77页111 图的基本概念二、一笔画问题1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树第10页/共77页12欧拉不仅证明了哥尼斯堡问题是不可能一笔画回到原出发点的，而且还证明了哥尼斯堡问题甚至不是可一笔画的。为了了解欧拉的结论，我们给出下列定义及定理。 1 图的基本概念二、一笔画问题定义：欧拉链定义（可一笔画的图）：我们可以笔不离纸地连续

7、画出该图，并且各边没有重复，即可以“一笔画”画出该图，我们称这种图为可一笔画的。 如果连通图有一条包括所有顶点，但各边只出现一次的路线，则称这个连通图为可一笔画的图。 v3v4v1v2v5v3v4v1v2v5第11页/共77页131 图的基本概念二、一笔画问题哈密尔顿图定义3-7（欧拉链）：经过且仅经过图中每条边一次的链称为欧拉链。 定义3-8（欧拉圈）：经过且仅经过图中每条边一次的圈称为欧拉圈。 定理3-1（欧拉链的充要条件）：连通图含有欧拉链的充分必要条件是图中奇点的个数为0或2。 定理3-2（欧拉圈的充要条件）：连通图含有欧拉圈的充分必要条件是图中不存在奇点。 定义3-8（欧拉图）：含有

8、欧拉圈的图称为欧拉图。 1857年，英国数学家哈密尔顿提出了一个与上述问题密切相关的问题，即一个图是否存在这样一条路线，该路线经过所有顶点，且每个顶点只经过一次？可以证明，这样的路线必定是一个圈，称为哈密尔顿圈。含有哈密尔顿圈的图称为哈密尔顿图。 哥尼斯堡人想走过七座桥，且每座桥只能走过一次，最后回到出发点，这样的想法是不可能实现的。 欧拉链的特点是经过图的所有边，且每条边只经过一次，但对是否经过所有顶点及通过各顶点的次数没有限制。 第12页/共77页141 图的基本概念二、一笔画问题三、中国邮路问题 (1)(2)(6)(4)(3)(5)哈密尔顿图，非欧拉图（有奇点） 欧拉图，非哈密尔顿图（无

9、奇点） 既是欧拉图又是哈密尔顿图的图是存在的 需要指出，我们已经知道欧拉图的判断准则，即所有顶点均为偶点（或不存在奇点），但是尚没有一个哈密尔顿图的判断准则。然而，哈密尔顿图是有一定实用价值的，如与其有密切关系的“巡回售货员问题”，即找出一条包含所有顶点的最短闭合路线（这里，城市为顶点，城市之间的距离为边的长度）。 参考消息2010.10.26：瞬间解出“巡回售货员问题，蜜蜂大脑击败电脑” 英国卫报网站10.24报道。伦敦大学皇家霍洛维学院的研究小组利用电脑控制的人造花朵测试蜜蜂的行为，发现大脑小如草籽的蜜蜂很快能够确定最短路线。目前电脑是通过穷比法来求解的。该问题对于依赖于交通流、互联网、供

10、应链的现代生活不无意义。第13页/共77页151 图的基本概念1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树三、中国邮路问题 第14页/共77页161 图的基本概念三、中国邮路问题 1. 问题描述 二、 中国邮路问题邮递员在投送报刊信件时，从邮局出发，一般每次都要走遍他所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择一条什么样的路线才能以尽可能少的路程走完所有的街道呢？这个问题是我国著名运筹学家管梅谷教授于1962年首先提出的，并给出了它的解法，因此国际上称为中国邮路问题。 在一个赋权图上，求一个圈，该圈经过图中每条边至少一次，并使圈中各边权值的总和为

11、最小。称经过每条边至少一次的圈为邮递员路线。中国邮路问题就是求最优的邮递员路线。 2. 定理1. 问题描述如何理解最优邮递员路线？欧拉图： 以邮局为始终点的一个欧拉圈就是最优邮递员路线。非欧拉图：邮路中的某些边必须重复，带有重复边且总权值最小的圈为最优邮递员路线。 能形成圈的重复边方案不止一个，这时的问题是重复哪些边最好。第15页/共77页171 图的基本概念三、中国邮路问题 2. 定理 定理 3-42. 定理 因为每条边与两个端点相关联，所以计算顶点的度时，每条边均使用了两次，所以全部顶点度的和等于边数的两倍。 定理3-3（顶点度之和与边数的关系）：说明：第16页/共77页181 图的基本概

12、念三、中国邮路问题 2. 定理 3中国邮路问题的求解思路 定理3-4（奇点个数奇偶性）：证明：对于任一个图G，奇点的个数必为偶数。（偶点个数更是偶数？） （1）点集分解： 偶点集合奇点集合：21VVV（度之和为奇数？偶数？当然偶数）（度之和为奇数？偶数？取决于奇点个数的奇偶性）（2）由定理3-3： qvdvdvdVvVvVv221 212VvVvvdqvd偶数 偶数（3）由于奇点集合中所有奇点的度之和为偶数， 所以奇点集合中所有奇点的个数必为偶数。第17页/共77页191 图的基本概念三、中国邮路问题 3中国邮路问题的求解思路 4中国邮路问题的求解方法 3.中国邮路问题的求解思路 两种情况：（

13、1）不存在奇点： 为欧拉图，以邮局为始终点的欧拉圈即为所求（2）存在奇点： 为非欧拉图，为形成圈，必须在某些边上重复一次或多次。此时，为了减少重复路线的长度，则需要考虑图中各边的权值。 ?消除奇点方法1 消除奇点方法2 重复边 消除奇点方法3 能消除奇点的方案很多，何为最佳？求解思路：在含有奇点的赋权连通图中，增加一些边，使得在新得到的图中不含奇点，并且使得增加边的权值总和最小。 第18页/共77页201 图的基本概念三、中国邮路问题 4中国邮路问题的求解方法 （1）增加边的确定方法 4.中国邮路问题的求解方法奇偶点作业法 关键步骤：（1）如何增加边，使图不含奇点？（2）如何判断增加边的总权值

14、最小？第19页/共77页211 图的基本概念三、中国邮路问题 4中国邮路问题的求解方法 （2）最小权值增加边的确定方法 （1）增加边的确定方法 （i）增加边必须是重复边（ii）增加边必须能消除奇点由于是连通图，奇点之间必存在链奇点之间的链不止一条在链上增加重复边，可满足要求既无引入新边，也不影响原来的偶点。方案当然不止一个将奇点两两相连，必能消除奇点因为奇点的个数为偶数增加边方法一增加边方法二但不能直接相连方法一的重复边长度不一定最短（边权以标示为准）第20页/共77页221 图的基本概念三、中国邮路问题 4中国邮路问题的求解方法 圈条件图示 （2）最小权值增加边的确定方法 定理3-5（最小权

15、值增加边的充要条件）设M是使图G不含奇点的所有增加边集合，则M中所有增加边权值总和为最小的充分必要条件为：（i）图G的每条边上最多增加一条边；（ii）在图G的每个圈上，增加边的总权值不超过该圈 原总权值的一半。（边条件）（圈条件）定理说明：（i）显然成立（ii）如果在图中某个圈上增加边的总权值超过该圈原总权值的一半，则去掉该圈的增加边，同时给该圈的其余边加上增加边。这样，图中仍不会出现奇点，但可使增加边的总权值减少到不超过该圈原总权值的一半。 第21页/共77页231 图的基本概念三、中国邮路问题 4中国邮路问题的求解方法 5奇偶点图上作业法的步骤 圈条件图示说明： w2w1，21121www

16、若21221www则必有第22页/共77页241 图的基本概念三、中国邮路问题 5奇偶点图上作业法的步骤 例 3-3 5奇偶点图上作业法的步骤 ： （1）找奇点，确定初始增加边。在每两个奇点间找一条链，在链经过的所有边上都增加一条边。 （2）检验定理3-5的两个条件是否满足，若满足则停止求解过程，否则转入第3步。 （3）调整增加边。 若某边不满足边条件 ：则从该条边上去掉偶数条增加边，以保证图中顶点仍全部是偶点； 若某圈不满足圈条件 ：则将这个圈上的增加边去掉，将该圈的其余边上增加边，并转回到第2步。 第23页/共77页251 图的基本概念三、中国邮路问题 例 33 四、子图和树 例3-3 求

17、图3-7（a）的最优邮递员路线。 v1v6v7v8v9v2v3v4v5494642553443解：不满足不满足（4）再检验点击，再选一个圈点击，显示“不满足”（5）再调整增加边点击，显示新增加边，点击，删除旧增加边（6）再检验全部13个圈均满足圈条件。最优路线总权值53+15686.讨论（1）难点（圈检验）（2）找最优路线（1）找奇点初始增加边总权值：21点击，显示奇点点击，显示增加边确定初始增加边（2）检验边条件圈条件满足先选择一个圈，点击（3）调整增加边调整后的增加边总权值：17，有所改善（点击）（4）再检验（5）再调整增加边（6）再检验（1）找奇点，确定初始增加边（2）检验边条件圈条件（

18、3）调整增加边7.启发（1）不同要求选用不同最短路线方法（2）边权如为时间、成本等，则（3）研究思路很重要第24页/共77页261 图的基本概念1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树四、子图和树第25页/共77页271 图的基本概念四、子图和树 子图图示 4. 子图和树 1. 子图（1）定义3-9（子图）当寻找一个图中的一部分符合某些条件时，即涉及到子图最简单的图为树，既连通，边数也最少即子图的全部或部分顶点和边都被原图包含（2）两种重要的子图（i）部分图全部顶点，部分边（ii）真子图部分顶点，部分边第26页/共77页281 图的基本概念四、子图和树

19、2. 树 v4v1v2v3v5(a) 图Gv4v1v2v3v5v4v1v2v5(b) 图G一个部分图一个部分图(c) 图G的一个真子图的一个真子图第27页/共77页291 图的基本概念四、子图和树 2. 树 树的定义 2. 树例3-4分析：（1）必须是连通图因要求任意两个城市之间均能互相通话如含圈，则从圈上去掉一条边，仍连通在6个城市v1， v2， v6之间架设电话线，要求任意两个城市之间均能互相通话，试说明对代表这个电话网的图有什么要求。 （2）必须不含圈满足例3-4要求的图v1v2v3v4v5v6特点：不含圈的连通图第28页/共77页301 图的基本概念四、子图和树 2. 树 关于树的定理

20、 （1） 树的定义定义3-10（树）一个无圈的连通图称为树，记作T （2） 树的性质性质1树中任意两点之间，有且仅有一条链。 因为树是连通的，所以任意两点之间必存在链。 又，如果两点之间有两条不同的链，则必有圈，这与树的定义相矛盾。 性质2若树中去掉任意一条边，则树成为不连通图。 由性质1, 树中任一条边是连接该边两个端点的唯一的一条链，所以去掉这条边后，其两个端点不再连通， 由该性质, 树中任一条边是连接该边两个端点的唯一的一条链， 该性质说明，在点集合相同的图中，树是边数最少的连通图。 第29页/共77页311 图的基本概念四、子图和树 2. 树 关于树的定理 关于树的定理定理3-6（顶点

21、数与边数的关系）证明：该性质说明，在点集合相同的图中，树是边数最少的连通图。 设树T的顶点数为P，则其边数为P-1。使用归纳法证明。（1）对于P2，定理显然成立。（1）设Pk时定理为真（即边数为k-1 ），证明Pk 1时定理成立第30页/共77页321 图的基本概念四、子图和树 2. 树 3图的部分树 v1v2v3v4v5v6Pk 1，边数？v1v2v3v4v5v6去掉一条边（边数？）端点重合Pk，边数？（由假设，k-1） 边数k-1+1k 新图：原图：第31页/共77页331 图的基本概念四、子图和树 3图的部分树 （2）求连通图部分树的方法 3. 图的部分树例3-5图中所示顶点 v1， v

22、2， v9代表9个城市，顶点之间的连线表示电话线架设的允许路线。要求任何两个城市之间都可以彼此通话（允许通过其它城市），并且电话线的根数最少，问满足要求的应是什么图？ （1）定义部分树的用途很广，因为它是包含图的所有顶点，但边数最少的连通图。 v1v6v7v8v9v2v3v4v5分析：（1）必须是原图的部分图（2）必须是连通图（3）必须无圈（如有圈，则有多余的边）（4）结果：必须是原图的部分树第32页/共77页341 图的基本概念四、子图和树 3图的部分树 （2）求连通图部分树的方法 例3-6 求部分树（避圈法） （2）求连通图部分树的方法 （i）避圈法先去掉图G的所有边，只留下点，然后每次任

23、意放回一条边，但应使其与已经放回的边不构成圈（避圈），反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。 （ii）破圈法在图G中任取一个圈，去掉圈上任意一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。 第33页/共77页351 图的基本概念四、子图和树 3图的部分树 （2）求连通图部分树的方法 例3-6 求部分树（破圈法） 例3-6 解：用避圈法求图3-12的一个部分树。 v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（1）按原图位置标出所有点（2）任意放一条边（3）依次放入其他边，注意避免形成圈问题：避圈法求得的图的部分树唯一？第34页/共

24、77页36v1v6v7v8v9v2v3v4v51 图的基本概念四、子图和树 3图的部分树 （2）求连通图部分树的方法 4. 最小部分树 例3-7 解：用破圈法求图3-12的一个部分树。 v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（1）任意选一个圈（2）任意去一条边（3）依次选其他圈，并破圈，直至无圈可破问题：破圈法求得的图的部分树唯一？有时只考虑边数最少还不够，还需要考虑总权值最小，这时应求最小部分树 第35页/共77页371 图的基本概念四、子图和树 4最小部分树(2) 求赋权连通图的最小部分树的方法 4. 最小部分树（1）最小部分树的定义定义3-12对于赋权连

25、通图G，其所有部分树中总权值最小的部分树，称为图G的最小部分树（或称最小树），记作T*，即 TWminTW*第36页/共77页381 图的基本概念四、子图和树 4最小部分树 (2) 求赋权连通图的最小部分树的方法 2 有向图（2） 求赋权连通图的最小部分树的方法（i）避圈法先去掉图G的所有边，只留下点，然后每次放回一条与已经放回的边不构成圈（避圈）且权值最小的边，反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。 （ii）破圈法在图G中任取一个圈，去掉圈上权值最大的一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。 请参考教材例3-8在一个赋权连通图中，可能存在权值相等

26、且最小的若干部分树，所以最小部分树可能不是唯一的。 第37页/共77页39主要内容2 有向图第三章 图与网络分析1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第38页/共77页402 有向图有向图的定义、基础图有向图的环、链、路2 有向图在前面讨论的图及赋权图中，涉及到的边都是无方向性的，即u，v=v，u，这种图称为无向图及赋权无向图。但在图论的应用中，经常遇到的情况是，不仅需要画出描述问题的图，而且需要指出图中每一条边的方向。这是因为，在有些问题中，一对顶点之间的关系往往不是对称的。例如，城市道路系统中的单行道、直流电

27、路等；另一方面，有些关系仅用无方向性的边是反映不出来的，例如，一项工程中各工序之间的先后关系、竞赛中的胜负关系等。 我们将点与点之间有方向的边称为弧，在图上用前头标明方向。 定义3-13基础图第39页/共77页412 有向图有向图的环、链、路链、路图示环链路注意链与路的区别。对于一条链，其各弧的方向与链的方向不一定一致；而对于路，其各弧的方向与路的方向一定是一致的。 回路始点与终点相同的路称为回路。 第40页/共77页422 有向图有向图的环、链、路3 图的矩阵表示v1v2v3v4v5a1a2a3a4a6a7a5链？ 路？链？ 路？链、路图示图的矩阵表示的用途（1）对于复杂的图，用矩阵描述简单

28、；（2）将优化算法在计算机上实现时，必须将图用矩阵来表示（如前述中国邮路问题）。第41页/共77页43主要内容3 图的矩阵表示第三章 图与网络分析1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第42页/共77页443 图的矩阵表示一、边矩阵二、邻接矩阵 一、边矩阵（弧矩阵） 3 图的矩阵表示定义3-14（边矩阵、弧矩阵） 设矩阵的行数为图的边（弧）数，列数为2，每行对应于图的一条边（弧），每行的两个元素为边（弧）的端点编号（对于有向图对于有向图，规定第一列元素为弧的始点编号，第二列元素为弧的终点编号），这样的矩阵称为图的

29、边（弧）矩阵。 v1v2v3v4a1a2a3a4a6a5324212143431Ba1a2a3a4a5a6始点终点邻接矩阵：最基本矩阵表示，可表示顶点之间的连通关系。本章求含负权弧网络最短路时须使用（弧矩阵） 第43页/共77页453 图的矩阵表示二、邻接矩阵 定义（续） 二、邻接矩阵定义3-15（邻接矩阵） 行、列数均等于图的顶点数，且矩阵元素aij符合下列规定的矩阵称为图的邻接矩阵： （1）对于有向图D： （2）对于无向图G： 的一条弧不是若的一条弧是若Dv，vDv，vajijiij01的一条边不是若的一条边是若Dv，vDv，vajijiij01第44页/共77页463 图的矩阵表示二、邻

30、接矩阵 邻接矩阵（例） （3）对于赋权有向图D ：（4）对于赋权无向图G： 的一条弧不是若的一条弧，且权值为是若Dv，vwDv，vwajiijjiijij的一条边不是若的一条边，且权值为是若Dv，vwDv，vwajiijjiijij第45页/共77页473 图的矩阵表示二、邻接矩阵 三、关联矩阵 有向图D v1v2v3v4a1a2a3a4a6a5的一条弧不是若的一条弧是若Dv，vDv，vajijiij01010100001101010043214321vvvvAvvvv关联矩阵，也称连接矩阵，用来表示顶点与边的连接关系。 邻接矩阵第46页/共77页483 图的矩阵表示三、关联矩阵 关联矩阵（例

31、）三、关联矩阵定义3-16（关联矩阵） （1）对于有向图D： （2）对于无向图G： 的端点不是其它情况流入的矢量向顶点若弧流出的矢量从顶点若弧jiijijijavvavas011不关联与边若顶点关联与边若顶点jijiijevevs01第47页/共77页493 图的矩阵表示三、关联矩阵 关联矩阵（无向图 例）有向图 的端点不是其它情况流入的矢量向顶点若弧流出的矢量从顶点若弧jiijijijavvavas011v1v2v3v4a1a2a3a4a6a50101101000111110000011014321654321vvvvSaaaaaa有向图的关联矩阵第48页/共77页503 图的矩阵表示三、关

32、联矩阵 4 最短路问题无向图 v1v2v3v4e1e2e3e4e6e5无向图的关联矩阵不关联与边若顶点关联与边若顶点jijiijevevs010101101000111110000011014321654321vvvvSeeeeee显然，图的边（弧）矩阵形式上最简单，但图的邻接矩阵和关联矩阵在连通性判断和某些优化计算中更具实用价值。一般情况下，一个图可由它的邻接矩阵和关联矩阵来完全决定。 第49页/共77页51主要内容4 最短路问题第三章 图与网络分析1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第50页/共77页524

33、 最短路问题一、定义 定义4 最短路问题一、最短路问题的定义 v6v1v2v3v4v5v7v837761622143例3-13 从油田v1到炼油厂v8铺设管道，管道路线限定范围如图3所示，弧的权代表路线长度，求使铺设路线长度最短的方案。 分析： 显然，在所给路线范围之内，从油田到炼油厂的铺设方案不止一个，且铺设路线长度不同，问题的要求是求铺设路线长度最短的方案。 （对于某些经过变形，可化为多阶段决策问题的最短路问题，可用动态规划方法求解） 第51页/共77页534 最短路问题一、定义 二、最短路算法定义3-17（最短路问题） n*nWminW11这种问题称为最短路问题。 应用举例： 管道铺设、

34、线路安排、厂区布局、设备更新等。 最短路问题不总是与距离有关的，也可以与时间、成本、流量、效率等有关，所以应用十分广泛。 第52页/共77页544 最短路问题二、最短路算法标号介绍二、最短路算法 两种情况： 1. 所有弧权为正狄克斯特拉（Dijkstra）算法 2. 存在负弧权情况（自学）Dijkstra算法又称标号法，由E. W. Dijkstra于1959年首先提出。目前公认，在所有弧的权值均为非负（即）的情况下，这个算法是寻求最短路的最好算法。这个算法不仅能给出从始点到终点的最短路，而且在求解过程中，实际还给出了从始点到图中任意一点的最短路。 1. 所有弧权为正狄克斯特拉（Dijkstr

35、a）算法 （1） Dijkstra算法 概述从v1开始，给每一个顶点一个有值标号，标号分为T标号和P标号两种。 第53页/共77页55其值表示从始点v1到vj的最短路的总权值，称为固定标号。 4 最短路问题二、最短路算法 标号介绍算法依据图示T标号T（vj）: P标号P（vj）: 其值表示从始点v1到vj的最短路总权值的上界，称为临时标号。 算法开始时，T(v1)=0, 其余T(vj)=+。 凡是得到P标号的顶点，说明已经求出v1到该点的最短路及最短路权值，其标号不再改变 。算法目标: 逐步求出始点v1到各T标号顶点的最短路，并将其改为P标号。当所有顶点均为 P标号时，算法结束。算法依据: 第

36、54页/共77页564 最短路问题二、最短路算法 算法依据图示（2）Dijkstra算法的求解步骤 反证法: 说明: v6v1v2v3v4v5v7v837761622143(1)16第55页/共77页574 最短路问题二、最短路算法 （2）Dijkstra算法的求解步骤 最小T标号改P标号的解释 （i） （2）Dijkstra算法的求解步骤 （ii） （iii） ijijjwvPvTminvT，旧新即现在vi到vj的最短路总权值上限有两个，选小者，向最短路总权值逼近 ？（下张幻灯片解释）如已无T标号，结束，否则转（ii） 第56页/共77页584 最短路问题二、最短路算法 （2）Dijkstr

37、a算法的求解步骤 例 3-14为什么只能将最小T标号的顶点改为P标号？ 至于与P标号顶点不直接相邻的其他顶点，其最短路更无法确定。而最小T标号顶点则一定与P标号顶点相邻（？）。目前只能确定的最短路目前尚不能确定其最短路v1P(vi)v1vi的最短路(已求出？)vi-1viT新(vj0)（最小）T新(vj1)（次之）T新(vj2)（最大）T新T新改P？所有T标号中的最小标号第57页/共77页594 最短路问题二、最短路算法 例3-14例3-14 求右图v1到v8之间的最短路 v6v1v2v3v4v5v7v837761622143解（1）列Dijkstra算法求解表。 单击（2）填写第一行。 单击

38、例 3-14（续）表头内容为顶点名称第58页/共77页60T=34 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（3）修改v2，v4的T标号例 3-14（续） 33012122，旧新minwvPvTminvT 77014144，旧新minwvPvTminvT第59页/共77页614 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（4）将v2改P标号并标路径例 3-14（续）T=3分析：能否将v4标为P标号？ 33012122，旧新minwvPvTminvT第

39、60页/共77页62T=74 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（5）例 3-14（续）修改v3，v5的T标号 107323233，旧新minwvPvTminvT 96325255，旧新minwvPvTminvT第61页/共77页634 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（6）例 3-14（续）T=7分析：此次为何能将v4标为P标号？将v4改P标号并标路径 77014144，旧新minwvPvTminvT第62页/共77页64 8179

40、45455minwvPvTminvT，旧新 114747477，旧新minwvPvTminvTT=84 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（7）例 3-14（续）修改v5，v7的T标号第63页/共77页654 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v837761622143（8）例 3-14（续）T=8将v5改P标号并标路径 817945455minwvPvTminvT，旧新第64页/共77页664 最短路问题二、最短路算法 例3-14（续）T=10例3-14（续） v6v1v2v3v4v5v7v837761622143（9）例 3-14（续）修改v6的T标号 113856566，旧新minwvPvTminvT第65页/共77页674 最短路问题二、最短路算法 例3-14（续）例3-14（续） v6v1v2v3v4v5v7v8