




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第七讲 图浙江大学 陈 越6.6 最短路径问题 若用带权图表示交通网,图中顶点表示地点,边代表两地之间有直接道路,边上的权值表示路程(或所花费用或时间) 。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。问题: 两地之间是否有通路? 在有多条通路的情况下,哪条最短? 考虑到交通网的有向性,直接讨论的是带权有向图的最短路径问题,但解决问题的算法也适用于无向图。 将一个路径的起始顶点称为源点,最后一个顶点称为终点。问题分类单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径(有向)无权图(有向)有权图多源最短路径问题:求任意两顶点间的最短路径6.6.1无权图的单源最短路算法
2、按照递增(非递减)的顺序找出固定顶点到各个顶点的最短路.Dijkstra算法(迪杰斯特拉)1.无权图的单源最短路算法0 v31 v1v42v2 2v5 30: 1: 2: v3v1 and v6v2 and v41 v6v7 33: v5 and v7在无权图中,经过顶点最少的路就是最短路。2.有权图的单源最短路算法从v1出发到v6的最短路径是:权重和最小的按照递增的顺序找出到各个顶点的最短路课本例题6.17用Dijkstra网图6.30中v0到所有其余顶点的最短路径。这是一个按距离递增的顺序逐步找出v0到所有其余顶点的最短路径的过程.D 表示存储v0到其余顶点的“当前最短距离”P 对应的最短
3、路径邻接于哪那个顶点初始时(第0步),数组D就是该图邻接矩阵表示时v0对应的行向量在D中选择到v0距离最小的顶点v1,可以断定,顶点v1已经找到了到v0的最短距离。因此, v1作为已经求得最短路径的顶点,通过绕行v1 , v0到其余顶点的当前最短距离很可能更短。选v1 (第1步),考虑v1的邻接点v2和 v3(不需考虑已经求得最短距离的v0 ,D1用灰色表示,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v3 ,通过绕行v3 , v0到其余顶点的当前最短距离很可能更短。选v3 (第2步),考虑v3的邻接点v5和 v6(不需考虑已经求得最短距离的v1和 v3 ,D1和D
4、3用灰色表示,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v6 ,通过绕行, v0到其余顶点的当前最短距离很可能更短。选v6 (第3步),考虑v6的邻接点v5和 v8(不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v2 ,通过绕行, v0到其余顶点的当前最短距离很可能更短。选v2 (第4步),考虑v2的邻接点v5和 v4(不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v5 ,通过绕行
5、, v0到其余顶点的当前最短距离很可能更短。选v5 (第5步),考虑v5的邻接点v4、 v8和 v7(不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v4 ,通过绕行, v0到其余顶点的当前最短距离很可能更短。选v4 (第6步),考虑v4的邻接点 v7(不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v8 ,通过绕行, v0到其余顶点的当前最短距离很可能更短。选v8 (第7步
6、),考虑v8的邻接点 v7和v9 (不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v7 ,通过绕行, v0到其余顶点的当前最短距离很可能更短。选v7 (第8步),考虑v7的邻接点 v9 (不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 、 v7 ,不参与下一步最短路径的选择) 因此,在数组D中选择到 v0距离最小的顶点v9 。选v9 (第9步)。(不需考虑已经求得最短距离的v0和 v1 、 v3 、 v6 、 v2
7、、 v5 、 v4 、 v8 、 v7 ,不参与下一步最短路径的选择) D1-D9表示从v0到v1-v9 的最短距离。通过搜索数组P得到最短路径,比如,v0到v9的最短路径可以这样得到:P9=7,P7=4,P4=5,P5=3,P3=1,P1=0,顺序到过来就是:v0,v1,v3 ,v5,v4,v7,v9.Dijkstra 算法令S=源点s + 已经确定了最短路径的顶点vi对任一未收录的顶点v,定义distv为s到v的最短路径长度,但该路径仅经过S中收集的顶点。即路径s(viS)v的最小长度若路径是按照递增(非递减)的顺序生成的,则真正的最短路必须只经过S中的顶点。每次从未收录的顶点中选一个di
8、st最小的收录增加一个v进入S,可能影响另外一个w的dist值!(v一定是s到w的路径上,v一定与w有一条直接的边)distw = mindistw, distv + 的权重的权重6.6.2多源最短路算法方法1:直接将单源最短路算法调用|V|遍T = O( |V|3 + |E|V|)方法2:T = O( |V|3 )对于稀疏图效果好算法对于稠密图效果好课本例题6.19用Floyd网图6.31中每一对顶点之间的最短路径。 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 0 6 114 0 2 3 0V12116V2V034最后得到的每对顶点之间的最短路径长度及其最短路径都应该分别是一个二维矩阵,分
9、别用二维数组D和二维数组P表示。Dij表示从vi到vj的最短路径长度,Pij表示从vi到vj的最短路径上vj的父顶点号。第一步 查看v0:0行0列以外的非对角元素,D12=2垂直和水平方向分别向0列0行投影两个元素之和D10+D02=4+11=15,因为152,所以D12=2保持不变。D21=,垂直和水平方向分别向0列0行投影两个元素之和D01+D20=3+6=9,因为93,所以D20=3保持不变。D02=11,垂直和水平方向分别向1列1行投影两个元素之和D01+D12=6+2=8,因为86,所以D01=6保持不变。D10=4,垂直和水平方向分别向2列2行投影两个元素之和D12+D20=2+3
10、=5,因为45,保持不变。下面考察最短路径矩阵P,与D的演变过程相对应:Pij=i的含义是:从vi到vj的最短路径中,vj的前驱结点(父结点)为vi,即初始假设直接的边就是最短路径。102100112多源最短路算法Floyd 算法Dkij = 路径 i l k j 的最小长度的最小长度D0, D1, , D|V|-1ij即给出了即给出了i到到j的真正最短距离的真正最短距离最初的D-1是什么?当Dk-1已经完成,递推到Dk时:或者k 最短路径 i l k j ,则,则Dk = Dk-1或者k 最短路径 i l k j ,则该路径必定由两,则该路径必定由两段最短路径组成: Dkij=Dk1ik+D
11、k1kj0123452030606515201080403570图图 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 20 60 10 65 30 70 40 35 20 15 80 表表 求最短路径时数组求最短路径时数组dist和和pre的各分量的变化情况的各分量的变化情况 初始化为Pathij=-1,表示从Vi到Vj 不经过任何(S中的中间)顶点。当某个顶点Vk加入到S中后使Aij变小时,令Pathij=k。 下表给出了利用Floyd算法求图的带权有向图的任意一对顶点间最短路径的过程。图图 带权有向图及其带权有向图及其邻接邻接矩阵矩阵 0 2 8 0 4 5 0V1482V2V05 表表 用用Floyd算法求任意一对顶点间算法求任意一对顶点间最短路径最短路径 0 2 8 0 45 0 0 2 8 0 4 5 7 0 0 2 6 0 4 5 7 0 0 2 6 9 0 4 5 7 0A -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 2 -1 -1 -1 0 -1PathS 0 0, 1 0, 1, 2 步骤步骤初态初态k=0K=1K=2根据上述
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 传统纺织工艺研究:手工印染技术的历史传承与创新应用
- 民警打分具体管理办法
- 供水公司主业管理办法
- 法兰西国族认同研究:从“国族传奇”看历史演变
- 民国茶叶消费量与产量动态关系研究
- 内部湿度差异对硬化水泥浆体特性的影响研究
- 公共物品维护管理办法
- 变频器效率优化-洞察及研究
- 跨界共生:“双师型”教师企业实践激励机制创新探讨
- 鞭毛状微生物阪崎肠杆菌的乳粉检测技术研究
- 办公室应聘题库及答案
- 2025年河北中考地理真题含答案
- 铁矿尾矿清运方案(3篇)
- 国开机考答案 管理学基础2025-06-27
- 国家开放大学《思想道德与法治》社会实践报告范文一
- 【9语安徽中考卷】2025年安徽省中考招生考试真题语文试卷(真题+答案)
- 2025年空气过滤器行业分析报告
- 同等学力人员申请硕士学位电子科学与技术学科综合水平全国统一考试大纲(第二版)
- (高清版)DG∕TJ 08-507-2018 高强混凝土抗压强度无损检测技术标准
- 2024年铁岭市三支一扶考试真题
- 2024版机电工程施工质量标准化数字模型图集
评论
0/150
提交评论