《广工管理运筹学第八章图与网络分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《广工管理运筹学第八章图与网络分析PPT讲稿.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、广工管理运筹学第八章 图与网络分析第1页，共74页，编辑于2022年，星期六引例哥尼斯堡七桥问题ABCDBDAC第2页，共74页，编辑于2022年，星期六环球旅行问题：第3页，共74页，编辑于2022年，星期六环球旅行问题的解另一个著名的问题:中国邮路问题第4页，共74页，编辑于2022年，星期六第第1节节 图与网络的基本知识图与网络的基本知识图可以用来做什么：图可以用来做什么：管理当中，事物及事物间的联系可以用图来描述管理当中，事物及事物间的联系可以用图来描述五只球队的比赛情况五只球队的比赛情况甲甲乙乙丙丙丁丁戊戊甲甲乙乙丙丙丁丁戊戊ABCD工作分配问题工作分配问题图已经应用于物质结构、交通
2、、信息传递等的描述图已经应用于物质结构、交通、信息传递等的描述第5页，共74页，编辑于2022年，星期六图与网络的基本概念（1）图：图：这里讨论的图由点以及点与点间的连线构这里讨论的图由点以及点与点间的连线构成，与平面几何的图不同，这里只关心图中有成，与平面几何的图不同，这里只关心图中有多少个点，点与点间有无连线，至于点与点间多少个点，点与点间有无连线，至于点与点间的连线是直线还是曲线，点的相对位置，则是的连线是直线还是曲线，点的相对位置，则是无关紧要的。无关紧要的。第6页，共74页，编辑于2022年，星期六图与网络的基本概念（2）定义定义1 一个图是由点集一个图是由点集V=vi和和V中的元素
3、的无中的元素的无序对的一个集合序对的一个集合E=ek所构成的二元组，记为所构成的二元组，记为G=(V,E)，V中的元素中的元素vi叫做叫做顶点顶点，E中的元素中的元素ek叫做叫做边边v2v1v5v3v4e2e1e3e4e5e6V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6e1=(v1,v1),e2=(v1,v2)例例第7页，共74页，编辑于2022年，星期六图与网络的基本概念（3）相邻相邻：图中的两点间存在连线（边），则称这：图中的两点间存在连线（边），则称这两点两点相邻相邻，并称它们是这条边的，并称它们是这条边的端点端点；若两；若两条边有公共的端点，则称这两条边条边有
4、公共的端点，则称这两条边相邻相邻，并，并称它们是其公共端点的称它们是其公共端点的关联边关联边。v2v1v5v3v4e2e1e3e4e5e6相邻相邻边数边数：m(G)=|E|顶点数顶点数：n(G)=|V|第8页，共74页，编辑于2022年，星期六图与网络的基本概念（4）无向边与无向图无向边与无向图：若图中任一条边的端点无序，：若图中任一条边的端点无序，即即(vi,vj)与与(vj,vi)是同一条边，则称它为是同一条边，则称它为无向边无向边，此时图称为此时图称为无向图无向图。有向图有向图：若图中边：若图中边(vi,vj)的端点是有序的，则的端点是有序的，则称它是称它是有向边有向边（或弧），（或弧）
5、，vi与与vj分别称为这条有分别称为这条有向边的向边的始点始点和和终点终点，相应的图称为，相应的图称为有向图有向图。第9页，共74页，编辑于2022年，星期六图与网络的基本概念（5）v2v1v5v3v4e2e1e3e4e5e6环环(自回路自回路)多重边多重边定义定义2 不含环和多重边不含环和多重边的图称为的图称为简单图简单图。含多。含多重边的图称为重边的图称为多重图多重图。简单图第10页，共74页，编辑于2022年，星期六图与网络的基本概念（6）定义定义3 每一对顶点间都有边相连的无向简单图称每一对顶点间都有边相连的无向简单图称为为无向完全图无向完全图；有向完全图有向完全图是指每一对顶点间有是
6、指每一对顶点间有且仅有一条有向边的简单图。且仅有一条有向边的简单图。完全图顶点数完全图顶点数n与边数与边数m间成立如下关系间成立如下关系:m=n(n-1)/2第11页，共74页，编辑于2022年，星期六图与网络的基本概念（7）定义定义4 图图G=(V,E)的点集的点集V可以分为两个非空子可以分为两个非空子集集X，Y，即，即X Y=V，X Y=，使得，使得E中的每中的每条边的两个端点中必有一个属于条边的两个端点中必有一个属于X，另一个属于，另一个属于Y，则称，则称G为为二部图二部图（偶图），有时记为（偶图），有时记为G=(X,Y,E)二部图非二部图第12页，共74页，编辑于2022年，星期六图与
7、网络的基本概念（8）定义定义5 以以v为端点的边数，叫做点为端点的边数，叫做点v的的次次(degree)，记作，记作deg(v),或简记为或简记为d(v)。v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3悬挂点悬挂点孤立点孤立点悬挂边悬挂边偶点偶点奇点奇点第13页，共74页，编辑于2022年，星期六图中顶点次的性质定理定理1 任何图中顶点次数的总和等于边数的任何图中顶点次数的总和等于边数的2倍。倍。定理定理2 任何图中次为奇数的顶点必有偶数个。任何图中次为奇数的顶点必有偶数个。定义定义6 在有向图中，以顶点在有向图中，以顶点v为始点的边数称为始点的边数称为顶点为顶点v的
8、的出次出次，记为，记为d+(v)；以；以v为终点的边数为终点的边数称为称为v的的入次入次，记为，记为d-(v)。顶点。顶点v的出次与入次的出次与入次的和称为点的和称为点v的的次次。第14页，共74页，编辑于2022年，星期六图与网络的基本概念（9）定义定义7 图图G=(V,E),若若E是是E的子集，若的子集，若V是是V的子的子集，且集，且E中的边仅与中的边仅与V中的顶点相关联，则称中的顶点相关联，则称G=(V,E)为图为图G的一个的一个子图子图，特别地，若，特别地，若V=V,则则称称G为为G的一个的一个生成子图（支撑子图）生成子图（支撑子图）。子图生成子图第15页，共74页，编辑于2022年，
9、星期六图与网络的基本概念（10）有时需要用图来表示事物及事物之间的定量的有时需要用图来表示事物及事物之间的定量的联系，这时图中除了顶点与边外，还有与点或联系，这时图中除了顶点与边外，还有与点或边有关的某些数量指标，常称它们为边有关的某些数量指标，常称它们为“权权”，权在图中可以表示距离、费用、通过能力等。权在图中可以表示距离、费用、通过能力等。这种点或边带权的图称为这种点或边带权的图称为网络网络（或（或赋权图赋权图）313112785342516第16页，共74页，编辑于2022年，星期六连通图（1）定义定义8 无向图中一个点、边交错的序列，序列无向图中一个点、边交错的序列，序列中的第一个和最
10、后一个元素都是点，若其中每中的第一个和最后一个元素都是点，若其中每条边以序列中位于它之前和之后的点为端点，条边以序列中位于它之前和之后的点为端点，则称这个点边序列为图中连接其第一个点与最则称这个点边序列为图中连接其第一个点与最后一个点的后一个点的链链。链中所含的边数称为。链中所含的边数称为链长链长。链，但只是链，但只是简单链简单链而而非非初等链初等链简单链：没有重复边；初等链：既无重复边也无重复点。对有向图可类似定义链，如果各边的方向一致，则称为道路。第17页，共74页，编辑于2022年，星期六连通图（2）定义定义9 若在无向图中，一条链的第一个点与最若在无向图中，一条链的第一个点与最后一个点
11、重合，则称这条链为后一个点重合，则称这条链为圈圈。只有重复点而。只有重复点而无重复边的圈为无重复边的圈为简单圈简单圈，既无重复点又无重复，既无重复点又无重复边的圈为边的圈为初等圈初等圈。初等圈初等圈非简单的圈非简单的圈第18页，共74页，编辑于2022年，星期六连通图（3）有向图有向图无向图无向图道路道路链（或道路）链（或道路）回路回路圈（或回路）圈（或回路）道路道路(边的方向一致边的方向一致)不是道路不是道路第19页，共74页，编辑于2022年，星期六连通图（4）定义定义10 一个图中一个图中任意任意两点间至少有一条链相连，两点间至少有一条链相连，则称此图为则称此图为连通图连通图。任何一个不
12、连通图总可以。任何一个不连通图总可以分为若干个连通子图，每一个称为原图的一个分为若干个连通子图，每一个称为原图的一个分图（分图（连通分支连通分支）。）。连通图连通图非连通图非连通图第20页，共74页，编辑于2022年，星期六图的矩阵表示邻接矩阵对于图对于图G=(V,E),|V|=n,构造一个矩阵构造一个矩阵A=(aij)n n,其其中：中：v1v2v3v4v5v6第21页，共74页，编辑于2022年，星期六图的矩阵表示权矩阵对于网络（赋权图）对于网络（赋权图）G=(V,E),|V|=n,其中边其中边(vi,vj)上有权上有权wij，构造一个矩阵，构造一个矩阵A=(aij)n n,其中：其中：3
13、42516v1v2v3v4第22页，共74页，编辑于2022年，星期六欧拉回路（1）定义定义13 连通图连通图G中，若存在一条道路，经过每中，若存在一条道路，经过每边一次且仅一次，则称这条道路为边一次且仅一次，则称这条道路为欧拉道路欧拉道路。若。若存在一条回路经过每边一次也仅一次，则称这条回存在一条回路经过每边一次也仅一次，则称这条回路为路为欧拉回路欧拉回路。具有欧拉回路的图称为欧拉图（具有欧拉回路的图称为欧拉图（E图）。图）。定理定理3 无向连通图无向连通图G是欧是欧拉图，当且仅当拉图，当且仅当G中无奇中无奇点点第23页，共74页，编辑于2022年，星期六欧拉回路（欧拉回路（2）推论推论1
14、无向连通图无向连通图G为欧拉图，当且仅当为欧拉图，当且仅当G的边集的边集可以划分为若干个初等回路。可以划分为若干个初等回路。推论推论2 无向连通图无向连通图G中有欧拉道路，当且仅当中有欧拉道路，当且仅当G中恰好有两个奇点。中恰好有两个奇点。ABCD哥尼斯堡七桥问题无解哥尼斯堡七桥问题无解一笔画问题一笔画问题第24页，共74页，编辑于2022年，星期六欧拉回路（3）定理定理4 连通有向图连通有向图G是欧拉图，当且仅当它的是欧拉图，当且仅当它的每每个顶点个顶点的出次等于入次。的出次等于入次。连通有向图连通有向图G有欧拉道路，当且仅当这个图中除了有欧拉道路，当且仅当这个图中除了两个顶点外，其余每个顶
15、点的出次等于入次，且这两个顶点外，其余每个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多两个顶点中，一个顶点的入次比出次多1，另一个的，另一个的入次比出次少入次比出次少1。v1v2v3v4v5v6第25页，共74页，编辑于2022年，星期六中国邮路问题一个邮递员，负责某一地区的信件投递，他每一个邮递员，负责某一地区的信件投递，他每天要走邮局出发，走遍该地区所有街道，再返天要走邮局出发，走遍该地区所有街道，再返回邮局，问应如何安排送信的路线可以使所走回邮局，问应如何安排送信的路线可以使所走的总路程最短？的总路程最短？用图论的语言描述就是：给定一个连通图用图论的语言描述就是：给定一个连
16、通图G，每边有非负权每边有非负权l(e)，要求一条回路过每边至少一，要求一条回路过每边至少一次，且满足总权最小。次，且满足总权最小。第26页，共74页，编辑于2022年，星期六中国邮路问题解法（1）若若G是欧拉图，则按欧拉回路走，就是满足要求是欧拉图，则按欧拉回路走，就是满足要求的经过每边至少一次且总权最小的走法。的经过每边至少一次且总权最小的走法。abcdef若若G中有奇点，则中有奇点，则G不是欧不是欧拉图，因此要连续地走过每拉图，因此要连续地走过每边至少一次，则必然有某些边至少一次，则必然有某些边不止一次走过。这相当于边不止一次走过。这相当于在在G中添加一些重复的边，中添加一些重复的边，使
17、得到的新图使得到的新图G*没有奇点没有奇点且满足总路程最短。且满足总路程最短。第27页，共74页，编辑于2022年，星期六中国邮路问题解法（2）abcdefabcdef对增加了重复边后得到的对增加了重复边后得到的新图新图G*，很明显其总权的，很明显其总权的大小取决于增加的重复边大小取决于增加的重复边权的大小。因此中国邮路权的大小。因此中国邮路问题转化为如下问题：问题转化为如下问题：在连通图在连通图G=(V,E)中，求一中，求一个边的集合个边的集合E1 E，将，将E1中中所有边都变成重复边得到所有边都变成重复边得到新图新图G*，使得，使得G*中无奇点，中无奇点，且且 最小最小第28页，共74页，
18、编辑于2022年，星期六中国邮路问题解法（3）上述问题的解决依赖于以下结果：上述问题的解决依赖于以下结果：定理定理5 已知图已知图G*=G+E1无奇点，则无奇点，则最小的充分必要条件为：最小的充分必要条件为：（1）每条边最多重复一次；）每条边最多重复一次；（2）对图）对图G中的每个初等圈来说，重复边的长中的每个初等圈来说，重复边的长度不超过圈长的一半。度不超过圈长的一半。第29页，共74页，编辑于2022年，星期六中国邮路问题解法（4）下面直观地说明，若定理下面直观地说明，若定理5的条件不成立，则的条件不成立，则可以得到总权比可以得到总权比E1的更小的重复边集。的更小的重复边集。1222541
19、22254重复两次或以上的重复两次或以上的去掉其中两条去掉其中两条将原来的重复边变成非重将原来的重复边变成非重复边，原来的非重复边变复边，原来的非重复边变成重复边成重复边第30页，共74页，编辑于2022年，星期六中国邮路问题解法（5）解法解法第一步第一步：确定初始可行方案。若图中没有奇：确定初始可行方案。若图中没有奇点，则它已经是欧拉图，按欧拉回路走即可。否点，则它已经是欧拉图，按欧拉回路走即可。否则，若有奇点，奇点必有偶数个，将奇点两两配则，若有奇点，奇点必有偶数个，将奇点两两配对，然后找出每对奇点间的一条道路，对，然后找出每对奇点间的一条道路，将此道路中的每条边将此道路中的每条边都变成重
20、复边。都变成重复边。524363459444第31页，共74页，编辑于2022年，星期六中国邮路问题解法（6）524363459444第二步第二步：调整可行方案。使重复边最多重复一次：调整可行方案。使重复边最多重复一次524363459444第32页，共74页，编辑于2022年，星期六中国邮路问题解法（7）524363459444第三步：检查图中每个初第三步：检查图中每个初等圈是否满足定理条件等圈是否满足定理条件（2），若不满足则进行），若不满足则进行调整。调整。524363459444524363459444第33页，共74页，编辑于2022年，星期六第三步要求检查每个初等圈，这一步可能是相
21、当繁琐的。例如上例中的图就包括下图所示的初等圈。第34页，共74页，编辑于2022年，星期六树树的概念定义定义14 连通且不含圈的无向图称为连通且不含圈的无向图称为树树。树中次。树中次为为1的点称为的点称为树叶树叶，次大于，次大于1的点称为的点称为分枝点分枝点。ABCDEFGHI J KLMN厂长厂长人人事事科科财财务务科科总总工工程程师师生生产产副副厂厂长长新新产产品品开开发发科科技技术术科科生生产产科科设设备备科科供供应应科科动动力力科科经经营营副副厂厂长长销销售售科科检检验验科科第35页，共74页，编辑于2022年，星期六树树的性质定理定理6 T=(V,E),|V|=n,|E|=m,则下
22、列关于树的说法是则下列关于树的说法是等价的。等价的。（1）T是一个树（即是一个树（即T是不含圈的连通图）是不含圈的连通图）第36页，共74页，编辑于2022年，星期六树树的性质（2）T无圈，且无圈，且m=n-1第37页，共74页，编辑于2022年，星期六树树的性质（3）T连通，且连通，且m=n-1第38页，共74页，编辑于2022年，星期六树树的性质（4）T无圈，但每加一新边就得到唯一的无圈，但每加一新边就得到唯一的一个圈一个圈T是边数最多的无圈是边数最多的无圈图图第39页，共74页，编辑于2022年，星期六树树的性质（5）T连通，但任舍去一边就不连通连通，但任舍去一边就不连通T是边数最少的连
23、通是边数最少的连通图图第40页，共74页，编辑于2022年，星期六树树的性质（6）T中任意两点有唯一一条链相连中任意两点有唯一一条链相连第41页，共74页，编辑于2022年，星期六生成树概念定义定义15 若图若图G的生成子图是一棵树，则称该树为的生成子图是一棵树，则称该树为图图G的的生成树（支撑树）生成树（支撑树），或简称为图，或简称为图G的树。的树。定理定理7 图图G有生成树的充分必要条件是图有生成树的充分必要条件是图G是连是连通的通的第42页，共74页，编辑于2022年，星期六生成树解法（1）避圈法避圈法这种方法是每步从连这种方法是每步从连通图中选出一条边，通图中选出一条边，使得它与已经选
24、出的使得它与已经选出的边不构成圈，直到选边不构成圈，直到选够够n-1条边为止。条边为止。一个图的生成树不是一个图的生成树不是唯一的。唯一的。第43页，共74页，编辑于2022年，星期六避圈法的另一种表述避圈法的另一种表述先去掉图G中所有边，只留下点，每次任意放回一条边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。5个顶点，4条边第44页，共74页，编辑于2022年，星期六生成树解法（2）破圈法破圈法这种方法是每步从这种方法是每步从连通图中选一个圈，连通图中选一个圈，并去掉该圈的一条并去掉该圈的一条边，直到图中不含边，直到图中不含圈为止。圈为止。第45页，共74页，编辑于20
25、22年，星期六另一种解法另一种解法第46页，共74页，编辑于2022年，星期六最小生成树概念定义定义16 连通图连通图G=(V,E),每条边上有非负权每条边上有非负权L(e)，一棵生成树上各边的权之和，称为这棵生成树的，一棵生成树上各边的权之和，称为这棵生成树的权，具有最小权的生成树，称为权，具有最小权的生成树，称为最小生成树（最最小生成树（最小支撑树）小支撑树），简称，简称最小树最小树。例如例如 如何用造价最省的电话线网将各有关单位连起来如何用造价最省的电话线网将各有关单位连起来的问题，就归结为求最小生成树的问题。的问题，就归结为求最小生成树的问题。354367124非最小树非最小树第47页
26、，共74页，编辑于2022年，星期六最小生成树解法1（Kruskal算法）避圈法：避圈法：这种方法每步从图中这种方法每步从图中挑选一条边，满足：挑选一条边，满足：（1）它与已经选出）它与已经选出的边不构成圈；（的边不构成圈；（2）它是满足条件（）它是满足条件（1）的权最小的边，直）的权最小的边，直到选够到选够n-1条边为止。条边为止。141213144553245214121314455324529个顶点，8条边第48页，共74页，编辑于2022年，星期六避圈法另一种表述先去掉图G的所有边，只留下顶点，每次放回一条权最小的边，使之与已经放回的边不构成圈，反复进行，直到有（n-1）条边为止。94
27、82333791423316个顶点，5条边第49页，共74页，编辑于2022年，星期六最小生成树解法（2）破圈法：破圈法：这种方法每步从图这种方法每步从图中任选一个圈，然中任选一个圈，然后去掉该圈中权最后去掉该圈中权最大的边，直到图中大的边，直到图中没有圈为止。没有圈为止。14121314455324529个顶点，8条边第50页，共74页，编辑于2022年，星期六破圈法举例破圈法举例948233379194823337916个顶点，5条边第51页，共74页，编辑于2022年，星期六破圈法举例破圈法举例v4v2v3v16215846最小生成树最小生成树的权的权=9/v4v2v3v1621546v
28、4v2v3v162154/v4v2v3v16214/v4v2v3v1621第52页，共74页，编辑于2022年，星期六根树定义定义17 若一个有向图在不考虑边的方向时是一若一个有向图在不考虑边的方向时是一颗树，则称这个图是颗树，则称这个图是有向树有向树。定义定义18 若有向树若有向树T恰有一个顶点的入次为恰有一个顶点的入次为0，其余，其余顶点的入次为顶点的入次为1，则称，则称T为为根树根树有向树有向树根树根树叶叶根根分枝点分枝点第53页，共74页，编辑于2022年，星期六根树的应用根树常用来表示指挥系统上下级的隶属关系，根树常用来表示指挥系统上下级的隶属关系，系统的分类、溯源与继承等关系。如管
29、理系统系统的分类、溯源与继承等关系。如管理系统的组织结构，家族谱系，计算机文件目录结构，的组织结构，家族谱系，计算机文件目录结构，数据结构等等。数据结构等等。第54页，共74页，编辑于2022年，星期六二叉树定义定义19 在根树中，若每个顶点的出次小于或在根树中，若每个顶点的出次小于或等于等于m，称这棵树为，称这棵树为m叉树叉树。若每个顶点的出次。若每个顶点的出次恰好等于恰好等于m或或0，则称它为，则称它为完全完全m叉树叉树。当上述的。当上述的m=2时，该树分别称为时，该树分别称为二叉树二叉树、完全二叉树完全二叉树。三叉树三叉树完全二叉树完全二叉树第55页，共74页，编辑于2022年，星期六最
30、优二叉树（霍夫曼树）实际问题中常需用到叶子上带权的二叉树，如实际问题中常需用到叶子上带权的二叉树，如信息处理中的最优检索、数据结构等问题。信息处理中的最优检索、数据结构等问题。令有令有s个叶子的二叉树个叶子的二叉树T各个叶子的权分别为各个叶子的权分别为pi，根到各叶子的距离（层次，即根到叶子的边数）根到各叶子的距离（层次，即根到叶子的边数）为为li(i=1,2,s)，则二叉树的总权数为，则二叉树的总权数为满足总权最小的二叉树称为满足总权最小的二叉树称为最优二叉树最优二叉树，也称为，也称为霍夫曼树霍夫曼树。第56页，共74页，编辑于2022年，星期六霍夫曼算法步骤：步骤：（1）将）将s个叶子按权
31、由小到大排列，不失个叶子按权由小到大排列，不失一般性，设一般性，设p1 p2 ps（2）将二个具有最小权的叶子合并成一个）将二个具有最小权的叶子合并成一个分枝点。然后令分枝点。然后令ss-1,若若s=1停止，否则转停止，否则转（1）。）。第57页，共74页，编辑于2022年，星期六1 2 2 3 3431 22 3 34351 2233435961 22334359615例例 s=6，权分别为，权分别为4,3,3,2,2,1.构造最小二叉树。构造最小二叉树。按霍夫曼算法构造最优二叉树如下：按霍夫曼算法构造最优二叉树如下：总权为：总权为：1 4+2 4+2 3+4 2+3 2+3 2=38第58
32、页，共74页，编辑于2022年，星期六例例 最优检索（最优检索（p270）510152050CDEBA153050100A?B?E?D?ABEDCYYYYNNNN最优二叉树最优二叉树最优检索流程最优检索流程m（T*）=54+10 4+15 3+20 2+50 1=195第59页，共74页，编辑于2022年，星期六最短路问题最短路问题是网络理论中应用最广泛的问题之一，最短路问题是网络理论中应用最广泛的问题之一，许多优化问题，如设备更新、管道铺设、线路安排许多优化问题，如设备更新、管道铺设、线路安排等都可以化为最短路问题求解。等都可以化为最短路问题求解。最短路问题的提法：设最短路问题的提法：设G=
33、(V,E)为连通图，图中为连通图，图中的各边的各边(vi,vj)有非负权有非负权lij(lij=表示表示vi,vj间无边间无边),vs,vt是图中任意两点，求一条道路是图中任意两点，求一条道路，使它是从，使它是从vs到到vt的所有道路中总权最小的道路。的所有道路中总权最小的道路。第60页，共74页，编辑于2022年，星期六Dijkstra算法原理原理：若：若(vs,v1,vn-1,vn)是是vs到到vn的最短路，则的最短路，则(vs,v1,vn-1)是是vs到到vn-1的最短路。的最短路。思路思路：采用标号法。使用两种标号，：采用标号法。使用两种标号，T标号和标号和P标标号，一个点的号，一个点
34、的P标号是永久性标号，表示起点到该标号是永久性标号，表示起点到该点最短路的权，它一旦给出就不再改变；而点的点最短路的权，它一旦给出就不再改变；而点的T标号是临时性的标号，表示对起点到该点最短标号是临时性的标号，表示对起点到该点最短路的权的估计值，当得到更精确的估计值时要路的权的估计值，当得到更精确的估计值时要修改原来的修改原来的T标号，此外算法的每一步要把某一个标号，此外算法的每一步要把某一个点的点的T标号改成标号改成P标号，当得到终点标号，当得到终点vt的的P标号时算标号时算法结束。法结束。第61页，共74页，编辑于2022年，星期六Dijkstra算法步骤第一步第一步：给：给vs点点P标号
35、标号P(vs)=0,其余点其余点T标号标号T(vi)=+第二步第二步：若：若vi为刚获得为刚获得P标号的点，则修改以标号的点，则修改以vi为起点的各边终点的为起点的各边终点的T标号为下两个数中的较小标号为下两个数中的较小者：一个是者：一个是vi的的P标号与该边权之和，另一个是标号与该边权之和，另一个是该终点原来的该终点原来的T标号。标号。第三步第三步：取所有具有：取所有具有T标号的点中标号的点中T标号值最小的标号值最小的点，将其点，将其T标号改为标号改为P标号。若本次得到标号。若本次得到P标号的标号的点为终点，算法终止，否则返回上一步。点为终点，算法终止，否则返回上一步。第62页，共74页，编
36、辑于2022年，星期六例（p251）46544779655410 465447796554104 6 给起点给起点P标号标号0，其余点其余点T标号标号（在在下面的求解过程中，下面的求解过程中，粉色粉色的数字为的数字为P P标号）标号）修改以刚获得修改以刚获得P标标号的点为起点的边号的点为起点的边的终点的的终点的T标号；然标号；然后将最小的后将最小的T标号改标号改成成P标号标号第63页，共74页，编辑于2022年，星期六465447796554104968 465447796554104968 第64页，共74页，编辑于2022年，星期六4654477965541049681314 465447
37、796554104968131417第65页，共74页，编辑于2022年，星期六465447796554104968131415465447796554104968131415最短路线见图最短路线见图第66页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v838422433123340 T(v2)=min(,0+4)=4,T(v3)=min(,0+8)=8黄色数字表示P标号最短路问题举例最短路问题举例第67页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v8384224331233404 8比较所有的T标号，4最小。所以P（v2）=44从v2出发，到v4,v
38、5。T(v4)=min(,4+3)=7,T(v5)=min(,4+4)=878第68页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v8384224331233404 8比较所有的T标号，7最小。所以P（v4）=74从v4出发，到v6。T(v6)=min(,7+3)=1078710第69页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v8384224331233404 8比较所有的T标号，8最小。所以P(v3)=P(v5)=84从v3出发，到v7,T(v7)=min(,8+3)=11从v5出发，到v8,T(v8)=min(,8+4)=127871088111
39、2第70页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v83842243312334048比较所有的T标号，10最小。所以P(v6)=104从v6出发，到v7,T(v7)=min(11,10+3)=11比较所有的T标号，11最小。所以P(v7)=11787108812101111第71页，共74页，编辑于2022年，星期六v1v2v3v4v6v5v7v838422433123340484从v7出发，到v8,T(v8)=min(12,11+3)=12P(v8)=12787881112101112第72页，共74页，编辑于2022年，星期六521658289972212102521112121057667991010633xy起点到该点起点到该点的最短距离的最短距离起点到该点的最起点到该点的最短距离的上界短距离的上界755对于无权图，可以采用类似的方法对于无权图，可以采用类似的方法第73页，共74页，编辑于2022年，星期六狄克斯托算法（狄克斯托算法（Dijkstra）的适用条件：）的适用条件：1、用于赋权有向图。、用于赋权有向图。对于赋权无向图的处理对于赋权无向图的处理2、权数、权数 wij 0第74页，共74页，编辑于2022年，星期六