最短路径Dijkstra算法.pptx

《最短路径Dijkstra算法.pptx》由会员分享，可在线阅读，更多相关《最短路径Dijkstra算法.pptx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1 最短路径最短路径两点之间的最短路径问题：求从某个源点到其余各点的最短路径求从某个源点到其余各点的最短路径每一每一对顶点之点之间的最短路径的最短路径第1页/共9页 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想:依依最短路径的长度最短路径的长度递增的次序求得递增的次序求得各条路径各条路径源点源点v1v2其中，从源点到从源点到顶点点v的最短路径的最短路径是所有最短路径中长度最短者。第2页/共9页2 Dijkstra2 Dijkstra算法算法单源最短路径问题是：给定带权的有向图G=（V，E），源点vV，求从v到V中其余各顶点的最短路径。如何求解上图

2、中的最短路径问题，Dijkstra提出了一种解决方案。第3页/共9页即迪杰斯特拉算法，其基本思想如下：设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径的长度。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。V0和k之间存在弧V0和k之间不存在弧第4页/共9页3）每次从集合V-S中取出具有最短特殊路径长度的顶点u，将u加到S中，同时对数组Dist做必要的修改。若若 Distu+ukDistk则将 Distk 改为 Distu+uk。其中，特殊路径特殊路径指从源点到u中间只经过S中顶点的路径。2）设置一个顶点集合S，存放最短路径

3、的终点。顶点k为当前最短路径的终点,将Vk 加入集合S中，而Distk为最短路径的长度。4)重复操作2）、3）共n-1次。由此求得图上其余各顶点的最短路径是依路径长度递增的序列。第5页/共9页若带权图G如下所示，根据上述算法来求解源点v0到v2的最短路径。第6页/共9页 根据以上分析和举例，不难得出狄杰斯特拉算法，其描述如下：Void shortestPath(MGraph G,int V0,PathMatrix&P,ShortPathTable&D)/Pv表示最短路径，Dv表示带权长度/Pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点/finalv为TRUE，即已经求得从v0到v的

4、最短路径 for（v=0;vG.vexnum;v+）finalv=FALSE;Dv=G.arcsv0v;for(w=0;wG.vexnum;w+)Pvw=FALSE;/设置空路径 if(DvINFINTY)Pvv0=TRUE;pvv=TRUE;第7页/共9页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&(min+G.arcsvwDw)Dw=min+G.arcsvw;Pw=Pv;Pww=TRUE;第8页/共9页感谢您的观看！第9页/共9页