单愿最短路径描述：给定带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到达路径各边权值之和。

      Dijkstra算法是解单源最短路径问题的贪心算法。Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪心选择来扩充集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪心扩充就是不断在集合S中添加新的元素（顶点）。

      初始时，集合S中仅含有源(origin)一个元素。设curr是G的某个顶点，把从源到curr且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径，并且使用数组distance记录当前每个顶点所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr，并将curr加入到集合S中，同时对数组distance进行必要的修改。一旦S包含了所有的V中元素，distance数组就记录了从源(origin)到其他顶点的最短路径长度。

算法演示[演示素材来源于网络|]

核心代码：

      Dijkstra描述：带权有向图G=(V,E),V={1,2,3,…}。顶点origin是源。数组distance[index]表示当前源到顶点index的最短路径长度。数组prev[index]表示源点到达index顶点最短路径的前一个顶点[Dijkstra只能获取最短路径的长度，通过prev记录前驱顶点可以很方便的获取详细的最短路径]。

      数据结构与代码：

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

public struct DIJGraph {      public int [] vexs;  //顶点信息      public int [][] arcs; //边的权值      public int num;     //顶点数目 }   public static bool DIJKSTRA( int origin,DIJGraph g,                 int [] distance, int [] prev) {      if (origin < 0 || origin >= g.num)          return false ;      bool [] s = new bool [g.num];        for ( int index = 0; index < g.num; ++index)      {          s[index] = false ;          distance[index] = g.arcs[origin][index];          prev[index] = (distance[index] == Int32.MaxValue) ? -1 : origin;      }      distance[origin] = 0;      s[origin] = true ;      for ( int i = 0; i < g.num; ++i)      {          int temp = Int32.MaxValue;          int curr = 0;          for ( int index = 0; index < g.num; ++index)          {              if (!s[index] && distance[index] < temp)              {                  curr = index;                  temp = distance[index];              }          }          s[curr] = true ;            for ( int index = 0; index < g.num; ++index)          {              if (!s[index] && g.arcs[curr][index] < Int32.MaxValue)              {                  int newDistance = distance[curr] + g.arcs[curr][index];                  if (newDistance < distance[index])                  {                      distance[index] = newDistance;                      prev[index] = curr;                  }              }          }      }      return true ; }

      贪心选择性质|最优子结构性质是Dijkstra算法所具备的。不过，虽然Dijkstra算法是解决单源最短路径的一款很优秀的算法，但是如果在图中存在多条最短路径，Dijkstra算法只能获取路径的长度，而无法给出最短路径的详细情况。即使在代码中添加distance[index]表示当前源到顶点index的最短路径长度。数组prev[index]来记录前驱点，但是一旦存在多条最短路径，我们只能获取最先遇到的那条（或者最后遇到的那条路径）[往往，我们偏向于获取的是最短路线而非路长]。总之，Dijkstra算法还有许多改进的地方。

      本文提供的核心代码使用C#实现，您可以点击[点击]。