![数据结构-基于C++语言(微课版) 课件 12-单源点最短路径问题_第1页](http://file4.renrendoc.com/view3/M03/01/1E/wKhkFmZegLyAHoxaAACIjXhvrls519.jpg)
![数据结构-基于C++语言(微课版) 课件 12-单源点最短路径问题_第2页](http://file4.renrendoc.com/view3/M03/01/1E/wKhkFmZegLyAHoxaAACIjXhvrls5192.jpg)
![数据结构-基于C++语言(微课版) 课件 12-单源点最短路径问题_第3页](http://file4.renrendoc.com/view3/M03/01/1E/wKhkFmZegLyAHoxaAACIjXhvrls5193.jpg)
![数据结构-基于C++语言(微课版) 课件 12-单源点最短路径问题_第4页](http://file4.renrendoc.com/view3/M03/01/1E/wKhkFmZegLyAHoxaAACIjXhvrls5194.jpg)
![数据结构-基于C++语言(微课版) 课件 12-单源点最短路径问题_第5页](http://file4.renrendoc.com/view3/M03/01/1E/wKhkFmZegLyAHoxaAACIjXhvrls5195.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
本节内容:单源点最短路径问题最短路径最短路径北京上海南京济南徐州280500320180160600260200青岛大连200问题引入:问题提出:
-如何求从上海到图中各城市的最短路径?
-如何求任意两个城市之间的最短路径?最短路径问题引入:用带权的有向图表示一个交通运输网,图中:顶点:表示城市
弧:表示城市间的交通路线
权值:表示此线路的长度或沿此线路运输所花的时间或费用等
最短路径:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径。最短路径最短路径弧上权值为非负情形的单源点最短路径问题问题描述:给定一个带权有向图G(权值均为非负)与源点v,求从v到G中其余各顶点的最短路径。求解方法:迪杰斯特拉(Dijkstra)算法算法思想:(1)集合S存放已求出的最短路径的终点,初始时S={v0},T={其余顶点},求出v0到T中顶点对应的距离值:若存在<V0,Vi>,为其弧上的权值;不存在<V0,Vi>,则为;(2)从T中选取一个其距离值为最小的顶点w,加入S,对T中顶点的距离值进行修改:若加进w作中间顶点,从V0到Vi的距离值比不加w的路径要短,则修改此距离值;(3)重复上述步骤,直到S中包含所有顶点,即S=V为止。最短路径迪杰斯特拉算法求最短路径<V0,V1>:13<V0,V2>:8<V0,V3>:
<V0,V4>:30<V0,V5>:
<V0,V6>:32从中选
V2<V0,V2>:8516432085623013717329G151643208562301371732913<V0,V1>8<V0,V2>
30<V0,V4>
32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>
32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6V0--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>最短路径迪杰斯特拉算法求最短路径S={V0
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2.Visual+FoxPro习题汇编及参考答案
- 投标书封面格式
- 《归去来兮辞并序》教学实录
- 小学六年级上学期数学《差倍问题》教学设计
- 统编版语文五年级上册第1-4单元教案
- 贵州遵义市桐梓县2025届初三下学期第三次四校联考语文试题含解析
- 食品干燥机械产品相关项目建议书
- 贵州省遵义市红花岗区2023-2024学年数学三下期末考试模拟试题含解析
- 轿跑车产品相关项目建议书
- 磁粉离合器项目可行性实施报告
- 返修返工控制方案
- 【最新】部编版六年级语文上册第7课《开国大典》优质教案+导学案
- 农业经济学试题库
- 年产2000吨凝固型酸奶生产车间工艺设计-8-13
- 装饰装修工程样板房施工方案
- 珍珠豆型小花生新品种“誉宇806”系列高产栽培技术农业种植技术栽培技术
- 血站物料管理程序
- 小学四年级下册综合实践活动.小拖鞋-(15张)ppt
- 非标设备电气设计规范要求
- 水稳基层施工方案
- 《机械制图》教案
评论
0/150
提交评论