版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、a,1,基本图算法陈嘉庆,a,2,最短路径问题,a,3,单源最短路径单源短路径,问题:具有有向图G(E,v ),并找到从给定源顶点s到另一顶点v的加权最小路径“最短路径”=“最小路径”的权重是路径上所有边的权重的总和。 /道路图:华师中山附中到市政府的最短路径是? 若a、4、顶点序列V0、V1、Vn为从V0到Vn的最短,则序列V0、V1、Vn-1必须为从V0到Vn-1的最短。 贪婪算法,权力非负的单源最短路径算法(Dijkstra ),a,5,v5,v4,v0,100,5,60,10,v1,v2,v3,20,50,30,图中从v0到各顶点的最短路径从: v0到v2 (v0 v3 )从50 v
2、0到v4 (v0,v4) 30 v0到v5 (v0,v4,v3,v5) 60,单一源的最短路径,a,6,基本思想:将图中的所有顶点分成两组:S,V-S,其中一组包含已确定的最短路径的顶点的集合s最初只包含源v0,在V-S中继续贪婪选择扩展集合s。权利非负的单源最短路径算法(Dijkstra )、a、7,权利非负的单源最短路径算法(Dijkstra )首先仅包含源v0,特殊路径:从源到g的某个顶点u的特殊路径,中间经过s的顶点的路径从源到u的特殊路径步骤: (1)将v0加在s上(2)将具有当前最短路径长度的顶点w加在s上。a,8,最短路径Dijkstra算法的例子,从1,0,12,3,(:1初始
3、化v,如果有边,则pathv=边; 如果选择disti=边缘的值,(disti为最小值,则pathi修正从1到I的最短路径,(3)修正接近I的路径,(4)重复(2)(3)、a, 9、最短路径Dijkstra算法描述方法如下: (其中,pathv和distv表示从v0到v的最短路径及其长度) (1)对于v0以外的各顶点vi,如果存在,则表示从v0到vi的(临时)最短路径和(2)从未解顶点中选择dist值最小的顶点v的话,现在的pathv和distv成为顶点v的最终解。 (3)如果某些顶点通过v,则从v0到该顶点的路径可能接近,因此需要更改这些顶点的路径及其长度值。 (4)重复(2)(3)直到所有的顶点都解决。 a,10,最短路径Dijkstra算法的例子,例如,0,12,3,(),(1,2 ),(1,3 ),(),(1,3,2 ),8,(1,3,4 ),(1,3,3,4 (1,3,5,a,11,狄克斯特算法:通常设定Distk=或=,辅助阵列Dist,各成分Disti表示从当前求出的源到其馀各顶点I的最短路径的长度。 a,12,1 )在从源点出发的所有圆弧中,如果选择权重最小的圆弧
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 人教版小学四年级下册数学 期末测试卷(预热题)
- 人教版小学四年级下册数学《期末测试卷》含答案【综合卷】
- 人教版小学四年级下册数学期末测试卷完整版
- 人教版小学四年级下册数学期末测试卷附参考答案(突破训练)
- 小学四年级下册数学《期末测试卷》附答案
- 小学数学四年级下册 期末测试卷附答案(预热题)
- 毕业晚会煽情主持词
- 小学数学六年级下册期末测试卷(易错题)
- 人教版六年级下册数学期末测试卷含完整答案(考点梳理)
- 小学六年级下册数学期末测试卷含完整答案【典优】
- 品牌宣传培训建立品牌特色
- 地质矿产勘测行业技能鉴定考试-地质专业人员晋升素质笔试(2018-2023年)真题摘选含答案
- 人教部编版语文九年级下册第五单元作业设计3
- 医疗设备技术培训方案
- 运动鞋的调查报告
- 北师大版二年级下册数学总复习教案
- 船舶维修工作内容解析
- 宫外孕失血性休克应急预案演练记录
- 矿山买卖授权委托书
- 2024年其他类-体育职业技能鉴定-武术教练笔试历年全考点试卷附带答案
- PKSolver药动学药效学数据处理软件.doc
评论
0/150
提交评论