源节点到１和２的距离分别为４和１０。因为它是从节点0直接相连的，我们取0 --> 1作为当前的最短路径，也就确定了0 --> 1的路径是全局里从节点0到节点１的最短路径，而不会有经过其他点到达节点１而形成更近的节点了。为什么会这样呢？因为我们当前选取的边已经是最小的了，没有比它更小的，所以就算我们选择到其他的边以后也可以连接到节点１，但是其他的边本身已经比边0 -- >1还要大，再加上其他的边连接，只会更大。所以我们就保证了当前取的这个最短边已经是全局最优了。
当然，在这里只是针对源节点连接的第一步，对于后续的节点呢？它们是否也符合这样的情况？按照前面的讨论。我们找到一个当前最短路径时，比如0 -- >1，我们就更新１的邻接节点，于是就有了0 -- > 4。这时计算出来的值是25。这个过程我们就可以假想为我们将节点１给消除了，只有一个从节点０直接连接到４而且长度为２５的边。而这个时候，我们再找到的最短路径就已经是0 -- >2了。它本身也相当于我们前面讨论的情况。针对源节点直接连接的点，最短的边也是全局范围内两个点之间最短的路径了。就这样继续不断的推演...
因此，对于Dijkstra算法，这里最核心的问题就是我们每次取出来的最短路径就是一个全局最优。我们可以将每次取出最短路径并更新邻接节点的过程看成是加入新的直连节点的过程。这样，我们就更容易理解这个问题了。
前提条件
我们前面的推导和讨论其实是基于两个条件的：
1. 图是连通的
2. 所有边的权值是正数。
对于条件１来说，如果图不是连通的，则我们从源节点到很多节点的边权值可以说是无穷大，这个时候就失去比较的意义了。而对于条件２，我们前面的推导里有提到。我们取的当前最小权值边是全局最优的。因为其他比这个边大的边再走若干步的路径到对应的节点会更大。而使得这个距离更大就是因为每一步的权值都是正数，所以我们可以每次放心的把原来的最小节点给删除。而如果出现权值为负数的情况，则还是可能出现从一个权值较大的边最终走到目的节点反而总权值更小。
数据结构的选取
根据问题的要求，最核心的问题就是我们需要用一个结构来表示图。我们可以用典型的邻接表方式来表示。当然，在这个问题里因为要有每个边之间的权值。我们可以在每个邻接表的元素里保存一系列对应的边。实现的时候可以定义一个专门的WeightedEdge对象。也可以用一个简单的Key value pair来表示。一个表示对应节点的编号，一个表示对应的权值。
因为要记录和更新到每个节点的距离值，我们可以用一个数组来记录它们，比如前面示例分析里用的dist[]数组。如果我们要记录最短路径节点，也可以用一个edgeTo[]数组来表示。每个索引位置的元素记录当前节点的前一个节点。
当然，还有一个比较重要的地方就是每次遍历更新的边信息。因为希望每次取权值最小的边。从这一点来说看起来我们可以用一个最小堆。但是因为在比较的过程中可能还需要更新表里面的值。所以有的实现是使用一个改进后的indexMinHeap。相当于对最小堆里的元素建了个索引。这种方式相对比较复杂，但是效率比较高。只是目前来说没有现成的类库支持。还有一种办法就是利用一个优先队列结合一个数组来实现。我在之前文章里也有过讨论。
和prim算法的差别
如果我们仔细看Dijkstra's algorithm会发现它和prim算法很像。因为它们都是根据一个给定的节点，然后扩展到整个图。但是如果仔细去看它们扩展的过程，我们会发现一些细微的差别。Dijkstra算法是计算到给定点最短距离的边，所以每次往外面扩展的时候是取当前最小权值的边再往表里面增加并更新原来的结果。而prim算法是计算到目前涵盖集合里最短的边，所以它不需要是到最开始源节点最短的距离，只要是到当前涵盖的节点集合里元素最近的那个就可以。所以每次它碰到的边不需要做任何加权值的运算而是直接加入到堆里，回头取最小的来判断处理就可以了。
总结
这篇文章算是对Dijkstra算法的一个思路重新推导。细微能够从一个更加直观的角度来理解整个过程。它本质上是利用了一个从某个节点连接的边里取到的最短的边就一定是全局来说最优的两点路径。所以每次在找到最短路径并更新邻接节点的时候，我们可以将它想象成去掉原来最短路径的点并形成新的更长的边的过程。