最短路

最短路

    典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？
 
    交通网络用有向网来表示：顶点——表示城市，弧——表示两个城市有路连通，弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。
    如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。
    问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n - 1条边。
   常见最短路径问题：单源点最短路径、所有顶点间的最短路径
（1）如何求得单源点最短路径？
    穷举法：将源点到终点的所有路径都列出来，然后在其中选最短的一条。但是，当路径特别多时，特别麻烦；没有规律可循。
    迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。
路径长度最短的最短路径的特点：
    在此路径上，必定只含一条弧 <v_0, v_1>，且其权值最小。由此，只要在所有从源点出发的弧中查找权值最小者。
下一条路径长度次短的最短路径的特点：
①、直接从源点到v_2<v_0, v_2>（只含一条弧）；
②、从源点经过顶点v_1，再到达v_2<v_0, v_1>,<v_1, v_2>（由两条弧组成）
再下一条路径长度次短的最短路径的特点：
    有以下四种情况：
    ①、直接从源点到v_3<v_0, v_3>（由一条弧组成）；
    ②、从源点经过顶点v_1，再到达v_3<v_0, v_1>,<v_1, v_3>（由两条弧组成）；
    ③、从源点经过顶点v_2，再到达v_3<v_0, v_2>,<v_2, v_3>（由两条弧组成）；
    ④、从源点经过顶点v_1  ,v_2，再到达v_3<v_0, v_1>,<v_1, v_2>,<v_2, v_3>（由三条弧组成）；
其余最短路径的特点:    
    ①、直接从源点到v_i<v_0, v_i>（只含一条弧）；
    ②、从源点经过已求得的最短路径上的顶点，再到达v_i（含有多条弧）。
Dijkstra算法步骤：
    初始时令S={v_0},  T={其余顶点}。T中顶点对应的距离值用辅助数组D存放。
    D[i]初值：若<v_0, v_i>存在，则为其权值；否则为∞。 
    从T中选取一个其距离值最小的顶点v_j，加入S。对T中顶点的距离值进行修改：若加进v_j作中间顶点，从v_0到v_i的距离值比不加 vj 的路径要短，则修改此距离值。
    重复上述步骤，直到 S = V 为止。

算法实现：

  

   

    

     

    
    

     

      void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
     
    
   

    

     

    
    

     

      { // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
     
    
   

    

     

    
    

     

          // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵，经过顶点变成TRUE
     
    
   

    

     

    
    

     

          // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
     
    
   

    

     

    
    

     

          int v,w,i,j,min;
     
    
   

    

     

    
    

     

          Status final[MAX_VERTEX_NUM];
     
    
   

    

     

    
    

     

          for(v = 0 ;v < G.vexnum ;++v)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              final[v] = FALSE;
     
    
   

    

     

    
    

     

              D[v] = G.arcs[v0][v].adj;        //将顶点数组中下标对应是 v0 和 v的距离给了D[v]
     
    
   

    

     

    
    

     

              for(w = 0;w < G.vexnum; ++w)
     
    
   

    

     

    
    

     

                  P[v][w] = FALSE;            //设空路径
     
    
   

    

     

    
    

     

              if(D[v] < INFINITY)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  P[v][v0] = TRUE;
     
    
   

    

     

    
    

     

                  P[v][v] = TRUE;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          D[v0]=0;
     
    
   

    

     

    
    

     

          final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
     
    
   

    

     

    
    

     

          for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
     
    
   

    

     

    
    

     

          { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
     
    
   

    

     

    
    

     

              min = INFINITY; /* 当前所知离v0顶点的最近距离 */
     
    
   

    

     

    
    

     

              for(w = 0;w < G.vexnum; ++w)
     
    
   

    

     

    
    

     

                  if(!final[w]) /* w顶点在V-S中 */
     
    
   

    

     

    
    

     

                      if(D[w] < min)
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     

                          v = w;
     
    
   

    

     

    
    

     

                          min = D[w];
     
    
   

    

     

    
    

     

                      } /* w顶点离v0顶点更近 */
     
    
   

    

     

    
    

     

                      final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
     
    
   

    

     

    
    

     

                      for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     

                          if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
     
    
   

    

     

    
    

     

                          { /* 修改D[w]和P[w],w∈V-S */
     
    
   

    

     

    
    

     

                              D[w] = min + G.arcs[v][w].adj;
     
    
   

    

     

    
    

     

                              for(j = 0;j < G.vexnum;++j)
     
    
   

    

     

    
    

     

                                  P[w][j] = P[v][j];
     
    
   

    

     

    
    

     

                              P[w][w] = TRUE;
     
    
   

    

     

    
    

     

                          }
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/87823902