院校资料系统工程.pptx

《院校资料系统工程.pptx》由会员分享，可在线阅读，更多相关《院校资料系统工程.pptx（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1主要内容1 图的基本概念1 图的基本概念第三章 图与网络分析一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第1页/共78页21 图的基本概念一、图、连通图、赋权图1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树第2页/共78页31 图的基本概念概述兰德公司简介概述（1）由来生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以用图与网络的形式进行描述（2）意义不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广泛应用（3）应用物理学、控制论、信息论、交通运输、经济管理、计算机科

2、学等（4）用例项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理布局等 第3页/共78页41 图的基本概念一、图、连通图、赋权图 1.图图论中的图与几何图形的区别一、图、连通图、赋权图1.图与以前在数学中学的几何图形不完全相同哥尼斯堡七桥问题：ABCD示意图图论中的图BDCe2e1e6e5e7e4e3A欧拉将此问题归结为一个“一笔画”问题，并证明了是不可能的，因为图中的每个点都与奇数条边相关联，不可能将这个图不重复地一笔画成，这是古典图论中一个著名问题。第4页/共78页51 图的基本概念一、图、连通图、赋权图 1.图图的基本概念图论中的图与几何图形的区别几何图形：强调几何要素（

3、如长度、角度、面积、形状等）的准确性（如桥的准确位置、长度、岛的面积大小）两个图在图论中完全相同图论中的图：不关注几何要素的准确性，强调点的数量及点之间关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥以及有几座桥）BDCe2e1e6e5e7e4e3AABCD第5页/共78页61 图的基本概念一、图、连通图、赋权图 1.图图的基本概念（续）图的基本概念顶点：定义3-1：ADBCe2e1e4e3e5e6端点：关联边：相邻点：相邻边：环：通常用点表示具体的或抽象的事物，而用边表示事物之间的某种联系。第6页/共78页71 图的基本概念一、图、连通图、赋权图 1.图图的基本概念（续）图的基本

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

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

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

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

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

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

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

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

12、第17页/共78页181 图的基本概念三、中国邮路问题 2.定理 3中国邮路问题的求解思路 定理3-4（奇点个数奇偶性）：证明：对于任一个图G，奇点的个数必为偶数。（偶点个数更是偶数？）（1）点集分解：（度之和为奇数？偶数？当然偶数）（度之和为奇数？偶数？取决于奇点个数的奇偶性）（2）由定理3-3：偶数 偶数（3）由于奇点集合中所有奇点的度之和为偶数，所以奇点集合中所有奇点的个数必为偶数。第18页/共78页191 图的基本概念三、中国邮路问题 3中国邮路问题的求解思路 4中国邮路问题的求解方法 3.中国邮路问题的求解思路 两种情况：（1）不存在奇点：为欧拉图，以邮局为始终点的欧拉圈即为所求（2

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

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

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

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

17、显示“不满足”（5）再调整增加边点击，显示新增加边，点击，删除旧增加边（6）再检验全部13个圈均满足圈条件。最优路线总权值53+15686.讨论（1）难点（圈检验）（2）找最优路线（1）找奇点初始增加边总权值：21点击，显示奇点点击，显示增加边确定初始增加边（2）检验边条件圈条件满足先选择一个圈，点击（3）调整增加边调整后的增加边总权值：17，有所改善（点击）（4）再检验（5）再调整增加边（6）再检验（1）找奇点，确定初始增加边（2）检验边条件圈条件（3）调整增加边7.启发（1）不同要求选用不同最短路线方法（2）边权如为时间、成本等，则（3）研究思路很重要第25页/共78页261 图的基本概念

18、1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树四、子图和树第26页/共78页271 图的基本概念四、子图和树 子图图示 4.子图和树 1.子图（1）定义3-9（子图）当寻找一个图中的一部分符合某些条件时，即涉及到子图最简单的图为树，既连通，边数也最少即子图的全部或部分顶点和边都被原图包含（2）两种重要的子图（i）部分图全部顶点，部分边（ii）真子图部分顶点，部分边第27页/共78页281 图的基本概念四、子图和树 2.树 v4v1v2v3v5(a)图Gv4v1v2v3v5v4v1v2v5(b)图G一个部分图(c)图G的一个真子图第28页/共78页291 图的基

19、本概念四、子图和树 2.树 树的定义 2.树例3-4分析：（1）必须是连通图因要求任意两个城市之间均能互相通话如含圈，则从圈上去掉一条边，仍连通在6个城市v1，v2，v6之间架设电话线，要求任意两个城市之间均能互相通话，试说明对代表这个电话网的图有什么要求。（2）必须不含圈满足例3-4要求的图v1v2v3v4v5v6特点：不含圈的连通图第29页/共78页301 图的基本概念四、子图和树 2.树 关于树的定理（1）树的定义定义3-10（树）一个无圈的连通图称为树，记作T（2）树的性质性质1树中任意两点之间，有且仅有一条链。因为树是连通的，所以任意两点之间必存在链。又，如果两点之间有两条不同的链，

20、则必有圈，这与树的定义相矛盾。性质2若树中去掉任意一条边，则树成为不连通图。由性质1,树中任一条边是连接该边两个端点的唯一的一条链，所以去掉这条边后，其两个端点不再连通，由该性质,树中任一条边是连接该边两个端点的唯一的一条链，该性质说明，在点集合相同的图中，树是边数最少的连通图。第30页/共78页311 图的基本概念四、子图和树 2.树 关于树的定理 关于树的定理定理3-6（顶点数与边数的关系）证明：该性质说明，在点集合相同的图中，树是边数最少的连通图。设树T的顶点数为P，则其边数为P-1。使用归纳法证明。（1）对于P2，定理显然成立。（1）设Pk时定理为真（即边数为k-1），证明Pk 1时定

21、理成立第31页/共78页321 图的基本概念四、子图和树 2.树 3图的部分树 v1v2v3v4v5v6Pk 1，边数？v1v2v3v4v5v6去掉一条边（边数？）端点重合Pk，边数？（由假设，k-1）边数k-1+1k 新图：原图：第32页/共78页331 图的基本概念四、子图和树 3图的部分树（2）求连通图部分树的方法 3.图的部分树例3-5图中所示顶点 v1，v2，v9代表9个城市，顶点之间的连线表示电话线架设的允许路线。要求任何两个城市之间都可以彼此通话（允许通过其它城市），并且电话线的根数最少，问满足要求的应是什么图？（1）定义部分树的用途很广，因为它是包含图的所有顶点，但边数最少的连

22、通图。v1v6v7v8v9v2v3v4v5分析：（1）必须是原图的部分图（2）必须是连通图（3）必须无圈（如有圈，则有多余的边）（4）结果：必须是原图的部分树第33页/共78页341 图的基本概念四、子图和树 3图的部分树（2）求连通图部分树的方法 例3-6 求部分树（避圈法）（2）求连通图部分树的方法（i）避圈法先去掉图G的所有边，只留下点，然后每次任意放回一条边，但应使其与已经放回的边不构成圈（避圈），反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。（ii）破圈法在图G中任取一个圈，去掉圈上任意一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。第34页/共78页3

23、51 图的基本概念四、子图和树 3图的部分树（2）求连通图部分树的方法 例3-6 求部分树（破圈法）例3-6 解：用避圈法求图3-12的一个部分树。v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（1）按原图位置标出所有点（2）任意放一条边（3）依次放入其他边，注意避免形成圈问题：避圈法求得的图的部分树唯一？第35页/共78页36v1v6v7v8v9v2v3v4v51 图的基本概念四、子图和树 3图的部分树（2）求连通图部分树的方法 4.最小部分树 例3-7 解：用破圈法求图3-12的一个部分树。v1v6v7v8v9v2v3v4v5v1v6v7v8v9v2v3v4v5（

24、1）任意选一个圈（2）任意去一条边（3）依次选其他圈，并破圈，直至无圈可破问题：破圈法求得的图的部分树唯一？有时只考虑边数最少还不够，还需要考虑总权值最小，这时应求最小部分树 第36页/共78页371 图的基本概念四、子图和树 4最小部分树(2)求赋权连通图的最小部分树的方法 4.最小部分树（1）最小部分树的定义定义3-12对于赋权连通图G，其所有部分树中总权值最小的部分树，称为图G的最小部分树（或称最小树），记作T*，即 第37页/共78页381 图的基本概念四、子图和树 4最小部分树 (2)求赋权连通图的最小部分树的方法 2 有向图（2）求赋权连通图的最小部分树的方法（i）避圈法先去掉图G

25、的所有边，只留下点，然后每次放回一条与已经放回的边不构成圈（避圈）且权值最小的边，反复进行，直到进行不下去为止（即继续放回任何边，都将构成圈）。（ii）破圈法在图G中任取一个圈，去掉圈上权值最大的一条边（破圈）。然后再取另一个圈，并破圈，直到图中没有圈为止。请参考教材例3-8在一个赋权连通图中，可能存在权值相等且最小的若干部分树，所以最小部分树可能不是唯一的。第38页/共78页39主要内容2 有向图第三章 图与网络分析1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第39页/共78页402 有向图有向图的定义、基础图有向图

26、的环、链、路2 有向图在前面讨论的图及赋权图中，涉及到的边都是无方向性的，即u，v=v，u，这种图称为无向图及赋权无向图。但在图论的应用中，经常遇到的情况是，不仅需要画出描述问题的图，而且需要指出图中每一条边的方向。这是因为，在有些问题中，一对顶点之间的关系往往不是对称的。例如，城市道路系统中的单行道、直流电路等；另一方面，有些关系仅用无方向性的边是反映不出来的，例如，一项工程中各工序之间的先后关系、竞赛中的胜负关系等。我们将点与点之间有方向的边称为弧，在图上用前头标明方向。定义3-13基础图第40页/共78页412 有向图有向图的环、链、路链、路图示环链路注意链与路的区别。对于一条链，其各弧

27、的方向与链的方向不一定一致；而对于路，其各弧的方向与路的方向一定是一致的。回路始点与终点相同的路称为回路。第41页/共78页422 有向图有向图的环、链、路3 图的矩阵表示v1v2v3v4v5a1a2a3a4a6a7a5链？路？链？路？链、路图示图的矩阵表示的用途（1）对于复杂的图，用矩阵描述简单；（2）将优化算法在计算机上实现时，必须将图用矩阵来表示（如前述中国邮路问题）。第42页/共78页43主要内容3 图的矩阵表示第三章 图与网络分析1 图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树2 有向图4 最短路问题3 图的矩阵表示第43页/共78页443 图的矩阵表

28、示一、边矩阵二、邻接矩阵 一、边矩阵（弧矩阵）3 图的矩阵表示定义3-14（边矩阵、弧矩阵）设矩阵的行数为图的边（弧）数，列数为2，每行对应于图的一条边（弧），每行的两个元素为边（弧）的端点编号（对于有向图对于有向图，规定第一列元素为弧的始点编号，第二列元素为弧的终点编号），这样的矩阵称为图的边（弧）矩阵。v1v2v3v4a1a2a3a4a6a5a1a2a3a4a5a6始点终点邻接矩阵：最基本矩阵表示，可表示顶点之间的连通关系。本章求含负权弧网络最短路时须使用（弧矩阵）第44页/共78页453 图的矩阵表示二、邻接矩阵 定义（续）二、邻接矩阵定义3-15（邻接矩阵）行、列数均等于图的顶点数，且

29、矩阵元素aij符合下列规定的矩阵称为图的邻接矩阵：（1）对于有向图D：（2）对于无向图G：第45页/共78页463 图的矩阵表示二、邻接矩阵 邻接矩阵（例）（3）对于赋权有向图D：（4）对于赋权无向图G：第46页/共78页473 图的矩阵表示二、邻接矩阵 三、关联矩阵 有向图D v1v2v3v4a1a2a3a4a6a5关联矩阵，也称连接矩阵，用来表示顶点与边的连接关系。邻接矩阵第47页/共78页483 图的矩阵表示三、关联矩阵 关联矩阵（例）三、关联矩阵定义3-16（关联矩阵）（1）对于有向图D：（2）对于无向图G：第48页/共78页493 图的矩阵表示三、关联矩阵 关联矩阵（无向图 例）有向

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

31、最短路问题的定义 v6v1v2v3v4v5v7v837761622143例3-13 从油田v1到炼油厂v8铺设管道，管道路线限定范围如图3所示，弧的权代表路线长度，求使铺设路线长度最短的方案。分析：显然，在所给路线范围之内，从油田到炼油厂的铺设方案不止一个，且铺设路线长度不同，问题的要求是求铺设路线长度最短的方案。（对于某些经过变形，可化为多阶段决策问题的最短路问题，可用动态规划方法求解）第52页/共78页534 最短路问题一、定义 二、最短路算法定义3-17（最短路问题）这种问题称为最短路问题。应用举例：管道铺设、线路安排、厂区布局、设备更新等。最短路问题不总是与距离有关的，也可以与时间、成

32、本、流量、效率等有关，所以应用十分广泛。第53页/共78页544 最短路问题二、最短路算法标号介绍二、最短路算法 两种情况：1.所有弧权为正狄克斯特拉（Dijkstra）算法 2.存在负弧权情况（自学）Dijkstra算法又称标号法，由E.W.Dijkstra于1959年首先提出。目前公认，在所有弧的权值均为非负（即）的情况下，这个算法是寻求最短路的最好算法。这个算法不仅能给出从始点到终点的最短路，而且在求解过程中，实际还给出了从始点到图中任意一点的最短路。1.所有弧权为正狄克斯特拉（Dijkstra）算法（1）Dijkstra算法 概述从v1开始，给每一个顶点一个有值标号，标号分为T标号和P

33、标号两种。第54页/共78页55其值表示从始点v1到vj的最短路的总权值，称为固定标号。4 最短路问题二、最短路算法 标号介绍算法依据图示T标号T（vj）:P标号P（vj）:其值表示从始点v1到vj的最短路总权值的上界，称为临时标号。算法开始时，T(v1)=0,其余T(vj)=+。凡是得到P标号的顶点，说明已经求出v1到该点的最短路及最短路权值，其标号不再改变。算法目标:逐步求出始点v1到各T标号顶点的最短路，并将其改为P标号。当所有顶点均为 P标号时，算法结束。算法依据:第55页/共78页564 最短路问题二、最短路算法 算法依据图示（2）Dijkstra算法的求解步骤 反证法:说明:v6v

34、1v2v3v4v5v7v837761622143第56页/共78页574 最短路问题二、最短路算法 （2）Dijkstra算法的求解步骤 最小T标号改P标号的解释（i）（2）Dijkstra算法的求解步骤（ii）（iii）即现在vi到vj的最短路总权值上限有两个，选小者，向最短路总权值逼近？（下张幻灯片解释）如已无T标号，结束，否则转（ii）第57页/共78页584 最短路问题二、最短路算法 （2）Dijkstra算法的求解步骤 例 3-14为什么只能将最小T标号的顶点改为P标号？至于与P标号顶点不直接相邻的其他顶点，其最短路更无法确定。而最小T标号顶点则一定与P标号顶点相邻（？）。目前只能确

35、定的最短路目前尚不能确定其最短路v1P(vi)v1vi的最短路(已求出？)vi-1viT新(vj0)（最小）T新(vj1)（次之）T新(vj2)（最大）T新T新改P？所有T标号中的最小标号第58页/共78页594 最短路问题二、最短路算法 例3-14例3-14 求右图v1到v8之间的最短路 v6v1v2v3v4v5v7v837761622143解（1）列Dijkstra算法求解表。单击（2）填写第一行。单击例 3-14（续）表头内容为顶点名称第59页/共78页60T=34 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（3）修改

36、v2，v4的T标号例 3-14（续）第60页/共78页614 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（4）将v2改P标号并标路径例 3-14（续）T=3分析：能否将v4标为P标号？第61页/共78页62T=74 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（5）例 3-14（续）修改v3，v5的T标号第62页/共78页634 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（6）例 3-14

37、（续）T=7分析：此次为何能将v4标为P标号？将v4改P标号并标路径第63页/共78页64T=84 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（7）例 3-14（续）修改v5，v7的T标号第64页/共78页654 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（8）例 3-14（续）T=8将v5改P标号并标路径第65页/共78页664 最短路问题二、最短路算法 例3-14（续）T=10例3-14（续）v6v1v2v3v4v5v7v837761622143（9）

38、例 3-14（续）修改v6的T标号第66页/共78页674 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（10）例 3-14（续）T=10将v3改P标号并标路径第67页/共78页68T=114 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（11）例 3-14（续）修改v8的T标号第68页/共78页694 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（12）例 3-14（续）T=11将v6或v7

39、改P标号并标路径第69页/共78页70T=114 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（13）例 3-14（续）修改v7，v8的T标号注意仍使用原路径第70页/共78页714 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（14）例 3-14（续）注意仍使用原路径T=11将v7改P标号并标路径第71页/共78页72T=134 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（15）例 3-1

40、4（续）两种情况均考虑修改v8的T标号第72页/共78页73T=134 最短路问题二、最短路算法 例3-14（续）例3-14（续）v6v1v2v3v4v5v7v837761622143（16）例 3-14（结果）两种情况均考虑P=11将v8改P标号并标路径第73页/共78页744 最短路问题二、最短路算法 例3-14（结果）例3-14（续）（17）例 3-14（结论）结果（全表）：第74页/共78页754 最短路问题二、最短路算法 例3-14（结果）例3-14（续）v6v1v2v3v4v5v7v837761622143（18）例 3-15结论：返回上页查看返回上页查看返回上页查看需要指出的是，Dijkstra算法只适用于所有弧的权值为非负的情况，若存在权值为负的弧，则算法失效，下面通过一个简单的例子来说明这一点。第75页/共78页764 最短路问题二、最短路算法 例3-14（结果）例3-15 第四章 网络计划技术Dijkstra算法求解表2.图中存在含负权弧时最短路的求解算法。（自学）说明能否用Dijkstra算法计算右图v1到v2的最短路。v1v2v3-321解Dijkstra算法得到的最短路：真正最短路：第76页/共78页77谢谢！请看下一章谢谢！请看下一章第77页/共78页78感谢您的观看！第78页/共78页