数据结构：最短路径算法ppt课件.ppt_第1页
数据结构：最短路径算法ppt课件.ppt_第2页
数据结构：最短路径算法ppt课件.ppt_第3页
数据结构：最短路径算法ppt课件.ppt_第4页
数据结构：最短路径算法ppt课件.ppt_第5页
已阅读5页，还剩24页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1，2020/8/9，图算法(2)，最短路径Shortest Path，青岛理工大学acm，2020/8/9，2，Dijkstra算法练习题链接Floyd算法练习题链接密码都是多条路径，哪条路径最短最短路径问题，2020/8/9，5，单源最短路径单源sourceshortestpath (Dijkstra算法)， 所有顶点对之间的最短路径问题all-pairsshortestpathh单个源最短路径Single-Source Shortest Path问题：具有有向图G(E，v )，并且找到从给定源顶点s到另一个顶点v的加权最小路径最短路径=最小权重路径的权重是路径上所有边的权重之和。 例如：

2、从道路图：青岛理工到金沙滩的最短路径，从2020/8/9、7、7、v5、v4、v0、100、5、60、10、10、v1、v2、v3、20、50、30 v4) 30 V0到v5 (V0、v4、v3、v5) 8、8、贪婪法：顶点列v0、V1、Vn从v0到Vn，权重不为负的单元最短路径算法(Dijkstra )，2020/8/9， 9、9、基本思想：将图中的所有顶点分成两组：S，V-S组是包含确定了最短路径的顶点的集合s，另一组是未确定的最短路径的顶点集合V-S最初只包含源v0，在V-S中继续进行贪婪选择扩展集合s 、非负权重的单元最短路径算法(Dijkstra )、2020/8/9，10、非负权重的单元最短路径算法(Dijkstra )，最初，s只包含源v0、特殊路径：源到g的任何顶点u (步骤3360 ) 、2020/8/9、11、v5、v4、v0、100、60、10、10、v1、v3、20、50、30、v2、v0vo Dijkstra演算法：通常，Distk=或=设定辅助阵列Dist，并设定各分量Dist 2020/8/9，14，1 )在从源点出发的所有圆弧中，选择权重最小的圆弧，即第一个最短路径。 2 )修正其他

人人文库> 全部分类> 教育资料 > 作文作品

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论