最短路径 Dijkstra

带权图的最短路径问题

1、带权图的最短路径问题
    　带权图的最短路径问题即求两个顶点间长度最短的路径。
其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。
    　路径长度的的具体含义取决于边上权值所代表的意义。
【例】交通网络中常常提出的如下问题就是带权图中求最短路径的问题。
      （1）两地之间是否有路相通?
      （2）在有多条通路的情况下，哪一条最短?
　　其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。

2、交通网络的表示
    　由于交通网络存在有向性，所以一般以有向网络表示交通网络。
【例】设A城到B城有一条公路，A城的海拔高于B城。若考虑到上坡和下坡的车速不同，则边<A，B>和边<B，A>上表示行驶时 间的权值也不同。即<A，B>和<B，A>应该是两条不同的边。

3、源点和终点
    习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。
    为了讨论方便，设顶点集V={0，1，…，n-1}，并假定所有边上的权值均是表示长度的非负实数。

单源最短路径问题
(Single-Source Shortest-PathsProblem)

    单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。

1、边上权值相等的有向网的单源最短路径
    　用求指定源点的BFS生成树的算法可解决

2、迪杰斯特拉(Dijkstra)算法求单源最短路径
    　由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。
（1）按路径长度递增序产生各顶点最短路径
    　若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。
【例】在有向网G8中，假定以顶点0为源点，则它则其余各顶点的最短路径按路径递增序排列如右表所示

（2）算法基本思想
    　设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
①初始化
    　初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。
②重复以下工作，按路径长度递增次序产生各顶点最短路径
    　在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。
    　当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
  注意：
    　①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
    　②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。

（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
    　根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
    　源点，红点1，红点2，…，红点n，蓝点k
 距离为：源点到红点n最短距离+<红点n,蓝点k>边长
    　为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。
    　若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V-S}，则D[k]=SD(k)。
    　初始时，每个蓝点v的D[c]值应为权w<s，v>，且从s到v的路径上没有中间点，因为该路径仅含一条边<s，v>。
  注意：
    　在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键

（4）k扩充红点集s后，蓝点集估计距离的修改
    　将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。
    　对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=<s，…，k，j>。且 D[j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。
    　所以，当length(P)=D[k]+w<k，j>小于D[j]时，应该用P的长度来修改D[j]的值。

（5）Dijkstra算法

 Dijkstra(G，D，s){
    //用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
    //以下是初始化操作
      S={s}；D[s]=0； //设置初始的红点集及最短距离
      for( all i∈ V-S )do //对蓝点集中每个顶点i
          D[i]=G[s][i]； //设置i初始的估计距离为w<s，i>
       //以下是扩充红点集
      for(i=0;i<n-1;i++)do{//最多扩充n-1个蓝点到红点集
           D[k]=min{D[i]：all i V-S}； //在当前蓝点集中选估计距离最小的顶点k
           if(D[k]等于∞)
                return； //蓝点集中所有蓝点的估计距离均为∞时，
                     //表示这些顶点的最短路径不存在。
           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₈ 以0为源点执行上述算法的过程及红点集、k和D向量的变化见【参见动画演示 】。
   　　　　　　　　　　　　　 <object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" width="151" height="192" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=5,0,0,0"> <param name="movie" value="../IMAGE/t7.18.swf"> <param name="quality" value="high"> <param name="wmode" value="transparent"> <embed type="application/x-shockwave-flash" width="151" height="192" src="file:///C%7C/Inetpub/wwwroot/web/IMAGE/t7.18.swf" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" wmode="transparent"></embed></object>

（6）保存最短路径的Dijkstra算法
    　设置记录顶点双亲的向量P[0．．n-1]保存最短路径：
　　当顶点i无双亲时，令P[i]=-1。
    　当算法结束时，可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径，只不过路径方向正好与从s到i的路径相反。
    　具体的求精算法【参见教材】 。
    　Dijkstra算法的时间复杂度为O(n² )

其他最短路径问题

    　最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决：
　　①单目标最短路径问题 (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的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。