最短路径算法课件.ppt

《最短路径算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.3单源最短路径给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。1、算法基本思想Dijkstra算法是解单源最短路径问题的贪心算法。8.3单源最短路径其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所

2、对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。8.3单源最短路径例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。8.3单源最短路径迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}31050306

3、04{1,2,4,3,5}510503060Dijkstra算法的迭代过程：初始状态下，S中只有一个点（源点v1）。-11-111010∞3010010000s:distance:path:①第二步，将S外距离S最近的点v2加入S。更新相应信息。-11-111010∞3010010000s:distance:path:1①②602第三步，将S外距离S最近的点v4加入S。更新相应信息。-11211010603010011000s:distance:path:1①②504④904第四步，将S外距离S最近的点v3加入S。更新相应信息。-1141401050309

4、011010s:distance:path:1①②603④③第五步，将S外距离S最近的点v5加入S。更新相应信息。-1141301050306011110s:distance:path:1①②④③⑤voidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint［n］;intminDis,i,j,u;//初始化三个数组//逐次将各点加入S//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u//标记顶点u

5、已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径voidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//从源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint［n］;intminDis,i,j,u;//初始化三个数组for(i=0;i

6、点v0已从集合T加入到集合S中//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;i

7、istance[j])distance[j]=distance[u]+G[u][j];path[j]=u;}}}2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要时间。这个循环需要执行n-1次，所以完成循环需要时间。算法的其余部分所需要时间不超过。7.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V=(b)(a)2819

8、6123L=029061∞0复习Dijkstra算法其基本思想是，