|
()算法基本思想 设S为最短距离已确定的顶点集(看作红点集)VS是最短距离尚未确定的顶点集(看作蓝点集) ①初始化 初始化时只有源点s的最短距离是已知的(SD(s)=)故红点集S={s}蓝点集为空 ②重复以下工作按路径长度递增次序产生各顶点最短路径 在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集以保证算法按路径长度递增的次序产生各顶点的最短路径 当蓝点集中仅剩下最短距离为∞的蓝点或者所有蓝点已扩充到红点集时s到所有顶点的最短路径就求出来了 注意 ①若从源点到蓝点的路径不存在则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径 ②从源点s到终点v的最短路径简称为v的最短路径;s到v的最短路径长度简称为v的最短距离并记为SD(v) ()在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集 根据按长度递增序产生最短路径的思想当前最短距离最小的蓝点k的最短路径是 源点红点红点…红点n蓝点k 距离为源点到红点n最短距离+<红点n蓝点k>边长 为求解方便设置一个向量D[n]对于每个蓝点v∈ VS用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有 中间点则必为红点)的最短路径长度(简称估计距离) 若k是蓝点集中估计距离最小的顶点则k的估计距离就是最短距离即若D[k]=min{D[i] i∈VS}则D[k]=SD(k) 初始时每个蓝点v的D[c]值应为权w且从s到v的路径上没有中间点因为该路径仅含一条边 注意 在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键 ()k扩充红点集s后蓝点集估计距离的修改 将k扩充到红点后剩余蓝点集的估计距离可能由于增加了新红点k而减小此时必须调整相应蓝点的估计距离 对于任意的蓝点j若k由蓝变红后使D[j]变小则必定是由于存在一条从s到j且包含新红点k的更短路径P=且 D[j]减小的新路径P只可能是由于路径和边组成 所以当length(P)=D[k]+w小于D[j]时应该用P的长度来修改D[j]的值 ()Dijkstra算法 Dijkstra(GDs){ //用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度 //以下是初始化操作 S={s};D[s]=; //设置初始的红点集及最短距离 for( all i∈ VS )do //对蓝点集中每个顶点i D[i]=G[s][i]; //设置i初始的估计距离为w //以下是扩充红点集 for(i=;i D[k]=min{D[i]：all i V-S}; //在当前蓝点集中选估计距离最小的顶点k if(D[k]等于∞) return; //蓝点集中所有蓝点的估计距离均为∞时， //表示这些顶点的最短路径不存在。Tw.WinGwiT.Com S=S∪{k}; //将蓝点k涂红后扩充到红点集 for( all j∈V-S )do //调整剩余蓝点的估计距离 if(D[j]>D[k]+G[k][j]) //新红点k使原D[j]值变小时，用新路径的长度修改D[j]， //使j离s更近。 D[j]=D[k]+G[k][j]; } } 【例】对有向网G 8 以0为源点执行上述算法的过程及红点集、k和D向量的变化见【 参见动画演示 】。 6)保存最短路径的Dijkstra算法 设置记录顶点双亲的向量P[0..n-1]保存最短路径： 当顶点i无双亲时，令P[i]=-1。 当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。 具体的求精算法【参见教材】 。 Dijkstra算法的时间复杂度为O(n 2 ) 其他最短路径问题 最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决： ① 单目标最短路径问题 (Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路 径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。 ② 单顶点对间最短路径问题 (Single-Pair Shortest-Path Problem)：对于某对顶点u和v，找出从u到v的一条最短路径 。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。 ③ 所有顶点对间最短路径问题 (All-Pairs Shortest-Paths Problem)：对图中每对顶点u和v，找出u到v的最短路径问题 。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。 |
