最短路径Dijkstra算法.ppt
《最短路径Dijkstra算法.ppt》由会员分享,可在线阅读,更多相关《最短路径Dijkstra算法.ppt(9页珍藏版)》请在三一文库上搜索。
1、最短路径Dijkstra算法,1 最短路径,两点之间的最短路径问题:,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,v2,其中,从源点到顶点v的最短路径是所有最短路径中长度最短者。,2 Dijkstra算法,单源最短路径问题是: 给定带权的有向图G=(V,E),源点vV,求从v到V中其余各顶点的最短路径。,如何求解上图中的最短路径问题,Dijkstra提出了一种解决方案。,即迪杰斯特拉算法,其基本思想如下:,设置辅助数组Dist,其中每个分量Distk 表示 当前所求得的从源点到其
2、余各顶点 k 的最短路径的长度。,1)在所有从源点出发的弧中选取一条权值最小的弧,即为第一条最短路径。,V0和k之间存在弧,V0和k之间不存在弧,3)每次从集合V-S中取出具有最短特殊路径长度的顶点u,将u加到S中,同时对数组Dist做必要的修改。若 Distu+G.arcsukDistk 则将 Distk 改为 Distu+G.arcsuk。 其中,特殊路径指从源点到u中间只经过S中顶点的路径。,2)设置一个顶点集合S,存放最短路径的终点。顶点k为当前最短路径的终点,将Vk 加入集合S中,而Distk为最短路径的长度。,4) 重复操作2)、3)共n-1次。由此求得图上其余各顶点的最短路径是依
3、路径长度递增的序列。,若带权图G如下所示,根据上述算法来求解源点v0到v2的最短路径。,根据以上分析和举例,不难得出狄杰斯特拉算法,其描述如下:,Void shortestPath(MGraph G,int V0, PathMatrix ,Dv0=0; finalv0=TRUE; /初始化,v0顶点在S集中 /开始主循环,每次求得v0到某个顶点v的最短距离,将v加到S集 for(i=1;iG.vexnum;i+) min=INFINITY; for(w=0;wG.vexnum;i+) /求得当前离v0顶点最近距离 if(!finalw) if(Dwmin) v=w; min=Dw; finalv=TRUE; /离v0最近距离顶点v加入S集 for(w=0;wG.vexnum;w+)/更新当前最短路径及距离 if(!finalw ,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 路径 Dijkstra 算法
链接地址:https://www.31doc.com/p-8920477.html