图的单源最短路径（Dijkstra算法）

在许多路由问题中，寻找图中一个顶点到另一个顶点的最短路径或最小带权路径是非常重要的提炼过程。正式表述为，给定一个带权有向图G = (V, E) , 顶点s到v中顶点t的最短路径为在边集E中连接s到t代价最小的路径。要做到这一点首先要解决更为一般的单源最短路径问题。在单源最短路径问题中，计算从一个起始顶点s到其他与之相邻顶点之间的最短路劲。

Dijkstra算法

解决单源最短路径问题的方法之一就是Dijkstra算法。Dijkstra算法会生成一颗最短路径树，树的根为起始顶点s， 树的分支为从顶点s到图G中所有其他顶点的最短路径。此算法要求图中的所有权值均为非负数。与Prim算法类似，Dijkstra算法也采用贪心算法，它总是将当前看起来最近的最短的边加入最短路径中。

从根本上来说，Dijkstra算法通过选择一个顶点，并不断探测与之相关的边，类似广度优先搜索，找出当前距离最近的点。

算法流程：

1. 求从顶点a开始的单源最短路径，就是图中每个点距离a的最短路。

1. 选定a，标记访问过了，首先初始化图中各点与a的距离，在实际代码中一般用一个数组dist[i]存放这个值，如果暂时不可达，存一个极大值在里面。如图，只有b,c 直接与a连接，这时候dist[b]=8,dist[c]=4。其它点的dist[i]=NaN,后面的运算就是不断更新这个dist数组。

1. 再选出dist最小的元素扩展，很明显是c，标记visit，这时候通过c点，f，E也产生一个新的与a的距离，这时候更新dist数组，他们之前与a的距离都是NaN，当然只要原来与a的距离大于通过c与a的距离，都需要更新。

1. 再找出非visit中dist最小的点，找到f，因为b, d, e都与f相邻，这时候比较通过f后与a的距离，如果比原来dist短，就更新dist。

1. 选择顶点b。

1. 在选择顶点d, e后形成最短路径。

Dijkstra算法实现：

1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Source node will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]