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

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

Dijkstra算法##

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

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

结合下图简要的说一下算法运行过程：

1. 求从顶点`a`开始的单源最短路径，就是图中每个点距离`a`的最短路。 2. 选定`a`，标记访问过了，首先初始化图中各点与`a`的距离，在实际代码中一般用一个数组`dist[i]`存放这个值，如果暂时不可达，存一个极大值在里面。如图，只有`b`,`c` 直接与`a`连接，这时候`dist[b]=8`,`dist[c]=4`。其它点的`dist[i]=NaN,`后面的运算就是不断更新这个`dist`数组。 3. 再选出`dist`最小的元素扩展，很明显是`c`，标记`visit`，这时候通过`c`点，`f`，`e`也产生一个新的与`a`的距离，这时候更新`dist`数组，他们之前与a的距离都是`NaN`，当然只要原来与`a`的距离大于通过`c`与`a`的距离，都需要更新。 4. 再找出非`visit`中`dist`最小的点，找到`f`，因为`b, d, e`都与`f`相邻，这时候比较通过`f`后与`a`的距离，如果比原来`dist`短，就更新`dist`。 5. 选择顶点`b`。 6. 在选择顶点`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[]