Dijkstra 算法描述：
创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
创建 SPT（Shortest Path Tree）集合 sptSet，用于存放包含在 SPT 中的顶点；
如果 sptSet 中并没有包含所有的顶点，则：
选中不包含在 sptSet 中的顶点 u，u 为当前 sptSet 中未确认的最短距离顶点；
将 u 包含进 sptSet；
更新 u 的所有邻接顶点的距离值；
伪码实现如下：
例如，下面是一个包含 9 个顶点的图，每条边分别标识了距离。
源顶点 source = 0，初始时，
sptSet = {false, false, false, false, false, false, false, false, false};
distSet = {0, INF, INF, INF, INF, INF, INF, INF, INF};
将 0 包含至 sptSet 中；
sptSet = {true, false, false, false, false, false, false, false, false};
更新 0 至其邻接节点的距离；
distSet = {0, 4, INF, INF, INF, INF, INF, 8, INF};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 1，则将 1 包含至 sptSet；
sptSet = {true, true, false, false, false, false, false, false, false};
更新 1 至其邻接节点的距离；
distSet = {0, 4, 12, INF, INF, INF, INF, 8, INF};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 7，则将 7 包含至 sptSet；
sptSet = {true, true, false, false, false, false, false, true, false};
更新 7 至其邻接节点的距离；
distSet = {0, 4, 12, INF, INF, INF, 9, 8, 15};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 6，则将 6 包含至 sptSet；
sptSet = {true, true, false, false, false, false, true, true, false};
更新 6 至其邻接节点的距离；
distSet = {0, 4, 12, INF, INF, 11, 9, 8, 15};
以此类推，直到遍历结束。
sptSet = {true, true, true, true, true, true, true, true, true};
distSet = {0, 4, 12, 19, 21, 11, 9, 8, 14};
最终结果为源顶点 0 至所有顶点的距离：
C#代码实现：
<a href="http://www.cnblogs.com/gaochundong/p/breadth_first_search.html" target="_blank">广度优先搜索</a>
<a href="http://en.wikipedia.org/wiki/Dijkstra" target="_blank">Dijkstra's algorithm</a>
<a href="http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/" target="_blank">Greedy Algorithms | Set 7 (Dijkstra’s shortest path algorithm)</a>
<a href="http://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html" target="_blank">Bellman-Ford 单源最短路径算法</a>
<a href="http://courses.csail.mit.edu/6.006/spring11/lectures/lec16.pdf" target="_blank">Introduction to Algorithms 6.006 - Lecture 16</a>
本文转自匠心十年博客园博客，原文链接：http://www.cnblogs.com/gaochundong/p/dijkstra_algorithm.html，如需转载请自行联系原作者