图的最短路径_dijkstra算法.ppt_第1页
图的最短路径_dijkstra算法.ppt_第2页
图的最短路径_dijkstra算法.ppt_第3页
图的最短路径_dijkstra算法.ppt_第4页
图的最短路径_dijkstra算法.ppt_第5页
已阅读5页，还剩24页未读， 继续免费阅读

下载本文档

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

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论