算法设计及分析 单点源最短路径.docVIP

单点源最短路径问题 问题：已知一个赋权有向图G=(V,E，w),求由G中某个指定的顶点v0出发到其它各个顶点的最短路径。 455010 45 50 10 35 30 30 20 15 10 20 15 V0 V2 V1 V4 V5 V3 路径 长度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v1 45 (4) v0v4 45 一个加权有向图从v0 从v0到其它各个顶点的最短路径 对于一般的单点源最短路径问题，我们采用逐条构造最短路径的办法，用迄今已生成的所有路径长度之和为最小作为贪心准则，因此，每一条单独的路径都必须具有最小长度。假定已经构造了k条最短路径，则下面要构造的路径应该是下一条最短长度的最小长度路径。现在这k条最短路径的终点之集记为S，为陈述方便，也将v0放于S中。如果V\S不是空集，则从v0到V\S中顶点的最短路径中应该有一条最短的，比如是v0到vk+1的最短路径P： P=v0u1…us-1 usvk+1 (5.7) 显然，P1=v0u1…us-1us应是v0到us的最短路径，因而由S的定义和选定的贪心准则，us应属于S，同理，路径P上其它顶点ui也都在S中。所以，由v0出发的新的最短路径一定是某个已有的最短路径向前延伸一步。如果用Dist(vi)记从v0到S中顶点vi的最短路径的长度，而图G中的顶点w依其属于S与否分别记之为S(w)=1或S(w)=0，则从v0出发，新的最短路径的长度应该是 (5.8) 满足(5.8)式的顶点w被选择加入S，新的最短路径就是从v0出发到w的最短路径,而此时的Dist(w)=D(S)，S被更新为,后者可以由更新w的（集合）特征值来实现：S(w)=1(原来S(w)=0).上述算法思想是Dijkstra(迪杰斯特)提出的。 Dijkstra最短路径算法伪代码 DijkstraPaths(v,COST,Dist,n)//G是具有n个顶点{1,2,…,n} //的有向图， v是G中取定的顶点，COST是G的邻接矩阵 boolean S[1:n]; real COST[1:n,1:n],Dist[1:n]; integer u,v,n,num,i,w; for i to n do //将集合S初始化为空 S(i)=0; Dist(i)=COST(v,i); endfor S(v)=1; Dist(v)=0; //首先将节点v记入S for num from 2 to n do //确定由节点v出发的n-1条最短路 选取顶点w使得； S(w)=1； while S(u)=0 do //修改S中结点通过S到达v的最短距离 Dist(u)=min{Dist(u),Dist(w)+COST(w,u)}; endwhile endfor 12 end DijkstraPath 这里，我们需要注意语句6和9。根据(5.8)式，被选择的新的最短路径的长度应该等于语句6中的，这可由语句9中的Dist值更新语句看出。因为当S变成S’=S?{w}后，Dist(u)(u不属于S’)值如果改变，则必然是由于从v到u的最短路径上含有顶点w，又由于从v到S’中其它顶点的最短路径不含有顶点w，所以w是从v到u的最短路径上最后一个内部顶点，故Dist(u)=min{Dist(u), Dist(w)+ COST(w,u)}。算法DijstraPath的正确性由此可以保证。