1，最短路径的概念：

       1，从有向图中某一顶点（起始顶点）到达另一顶点（终止顶点）的路径中，其权值之和最小的路径；

      

2，问题的提法：

 

       1，给定一个带权有向图 G 与起始顶点 v，求从 v 到 G 中其它顶点的最短路径（每条边上都存在有意义的权值）；

       2，Dijkstra 算法核心是通过已知最短路径寻找未知最短路径；

      

3，解决思路：

       1，Dijkstra 提出按路径长度的递增次序，逐步产生最短路径；

              1，首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从起始顶点 v 到其它各顶点的最短路径全部求出为止；

       2，核心是通过递归的方式将从起始顶点到其他各顶点的最短路径全部求出来；

      

4，准备工作：

       1，辅助数组：Array<E> dist；

              1，dist[i] 表示当前从起始顶点 v0 到顶点 vi 的路径长度；

       2，初始设置：

              1，若从起始顶点 v0 到顶点 vi 有边：dist[i] 为该边上的权值；

              2，若从起始顶点 v0 到顶点 vi 无边：dist[i] 为无穷大；

             

5，Dijkstra 算法演示：

 

       1，由非空顶点集和边集这两个图的基本定义可知，集合在图的算法分析中的重要性，而集合在数据结构中常表现为数组；

       2，每次关注的是刚刚加入 S 集合的顶点到其他顶点的连接，通过刚刚求得的最短路径值来求出抵达其他顶点的可能的最短路径值，这就是核心；

         

6，Dijkstra 算法步骤：

 

7，Dijkstra 算法精髓：

       1，S 集合内的顶点是已经找到最短路径的顶点；

       2，v0 到 w 的最短路径只能通过 S 集内的顶点；

       3，dist[w] 可能改变：

 

             

8，如何记录最短路径上的各个顶点？

       1，定义辅助数组：

              1，Array<int> path；

                     1，path[i] 表示当前路径上的顶点 i 的前驱顶点；

                     2，初始化：path = {-1}；

                     3，修改：

                           

                          

9，Dijkstra 算法流程图：

 

10，Dijkstra 最短路径算法：

1 　　 /* 两个顶点之间最短路径，返回的数组表示两个最短路径上面的顶点 */ 2     SharedPointer< Array
     
       > dijkstra(int i, int j, const E& LIMIT)  // O(n*n) 3     { 4         LinkQueue
      
        ret;  // 保存最短路径上面的顶点 5  6         if( (0 <= i) && (i < vCount()) && (0 <= j) && (j < vCount()) ) 7         { 8             DynamicArray
       
         dist(vCount());  // 用于存储路径值 9             DynamicArray
        
          path(vCount());  // 用于存储当前结点的前驱结点10             DynamicArray
         
           mark(vCount());  // 标记顶点是否进入 S 集合11 12             /* 原材料初始化 */13             for(int k=0; k
          

s;61 62 s.push(j); // 终止顶点 j 先放入栈中；63 64 /* 将从起始顶点 i 到终值顶点 j 的点先放到栈中去；前驱结点的访问方式、值当做位置；值就是前面的顶点，所以直接把值压入进栈*/65 for(int k=path[j]; k!=-1; k=path[k])66 {67 s.push(k);68 }69 70 /* path 中保存的顶点顺序是逆序的，通过栈中转下，调整过来； */71 while( s.size() > 0 )72 {73 ret.add(s.top());74 75 s.pop();76 }77 }78 else79 {80 THROW_EXCEPTION(InvalidParameterException, "Index

is invalid ...");81 }82 83 /* 最终最短路径经历顶点数至少有 2 个，否则 i 到 j 是不可达的，最多多少顶点是不知道的 */84 if( ret.length() < 2 )85 {86 THROW_EXCEPTION(ArithmeticException, "There is no path from i to j ...");87 }88 89 return toArray(ret); // 放到数组里面90 }