Dijkstra算法
Dijkstra算法是图算法中最最常见的，也是最基础的，知名度最高的算法。
算法用途
解决带权重的有向图的单源最短路径问题，其中所有边的权重为非负值。一种贪婪算法。
算法描述
从源点起重复选择到源点最近路径的结点，并且修正未选择结点到源点的最短路径，只到所有结点全部选择到。
算法实现过程
算法实现的过程如下图表所示：
参考《数据结构与算法分析-Java语音描述》，推荐阅读，很不错。这里把图和表适当的修改，更加简洁清楚。喜欢深入研究的推荐这本书和《算法导论》。
图中要找到从源点V1到其他各点的最短路径。
-
图1-1和表1-1，是初始化的图的形态，V1为源点，其他点目前均是不可达的状态，而且未被选中。
图1-1
表1-1 -
寻找源点V1可以达到的邻接结点，V2和V4，修改与源点的距离，找到更小距离的结点V4。
图1-2
表1-2 -
V4被选中，找它未被选中的邻接结点V3、V5、V6和V7，更新这四个邻接结点与源点的距离，找到可达结点中更小距离的结点V2。
图1-3
表1-3 -
V2被选中，其未被选中邻接结点V5，经过V2到达的距离为12，大于当前的3，不更新结点与源点的距离。在当前可达结点中找到最小距离的结点V5（也可能是V3，因为距离都是3，由算法随机遍历选中的，这里选中V5）。V7是V5唯一的临界结点，经过V5达到V7的距离是9，小于当前的距离5，不需要调整。
图1-4
表1-4 -
然后选择V3，其未被选中的邻接结点为V6。经过V6到达V6的距离为3+5=8，小于当前9，更新V6与源点的距离。
图1-5
表1-5 -
余下的两个节点V6和V7，选中V7。到达V6的距离，经过V7后更新为5+1=6（6小于当前的8）。
图1-6
表1-6 -
最后选择V6。至此，找到源点到所有结点的最短路径。
图1-7
表1-7
算法总结
Dijkstra算法是典型的贪婪算法，每一步都是在当前基础上寻找最短距离的结点，直到所有结点被选中，算法结束。按照图示一步步的模拟算法的执行过程对于算法的理解很有帮助。
