最短路径算法.ppt

8.3 单源最短路径 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1、算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。 8.3 单源最短路径 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 8.3 单源最短路径 例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。 8.3 单源最短路径 初始状态下，S中只有一个点（源点v1）。 第二步，将S外距离S最近的点v2加入S。更新相应信息。 第三步，将S外距离S最近的点v4加入S。更新相应信息。 第四步，将S外距离S最近的点v3加入S。更新相应信息。 第五步，将S外距离S最近的点v5加入S。更新相应信息。 void Dijkstra ( int G[][N],int v0,int distance[], int path[]，int n) //源点v0到其他顶点的最短距离distance和最短路径下标path { int *s=new int［n］; int minDis, i, j, u; ? //初始化三个数组 //逐次将各点加入S //在当前还未找到最短路径的顶点集中 选取具有最短距离的顶点u //标记顶点u已从集合T加入到集合S中 //修改从v0到其他顶点的最短距离和最短路径 void Dijkstra ( int G[][N],int v0,int distance[], int path[]，int n) //从源点v0到其他顶点的最短距离distance和最短路径下标path {int *s=new int［n］; int minDis , i, j, u; ? //初始化三个数组 for(i=0;in;i++) { distance［i］=G[v0][i]; s［i］=0; if(I != v0 distance［i］MAX) path［i］=v0; else path［i］=-1; } s［v0］=1;//标记顶点v0已从集合T加入到集合S中 //在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u for(i=1;in;i++) {minDis=MAX; for(j=0;j=n;j++) if(s［j］==0distance［j］minDis) {u=j; minDis=distance［j］; } s［u］=1;//标记顶点u已从集合T加入到集合S中 //修改从v0到其他顶点的最短距离和最短路径 for(j=0;jn;j++) if( s[j]==0G[u][j]MAX distance[u]+G[u][j]distance[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)，求所有顶点之间的最短路径和最短距离。 复习Dijkstra算法 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且