简介
Dijkstra's algorithm是一个求图中单点到其他所有点最短距离的算法。我在之前的一篇文章里也有过一些讨论。只是那篇文章写得比较仓促，对于该算法的思想和推导理解得也并不深刻。经过一些时间的思考，这里想对该算法的思想做一个进一步的阐述，并对一些和它相关的问题进行比较讨论。
算法描述分析
对于这个算法来说，它有这么一个前提。在一个连通的图中(可以是有向图或者无向图)，所有的边都有一个对应的权值。我们给定一个起点，需要求基于这个起点到所有其他节点的最短路径。为了解决这个问题，Dijkstra's algorithm的解决步骤如下：
１．设定给定源节点到自身的边权值为0，而到所有其他节点的权值为无穷大。
２．找到距离起点最短的边，因此找到对应的一个节点。这个节点是从起点开始能找到的最近的点。
３．查找是否有到这个最近点的邻接点更短的路径，如果有，则更新这些路径值。
４．重复上述步骤2, 3直到涵盖所有节点。
在讨论这个算法的具体正确性以及复杂度之前，我们先以下图为例用上述的步骤来推导一下。
假定图中的红色节点是我们指定的起点。同时我们用一个数组来表示从源节点到其他节点的最短距离。那么，我们按照前面的步骤来说，对于红色节点本身来说，它最短的边就是到它自身的，而且长度为0。这个时候，我们所知的边如下表：
| 边 | 权值 |
| 0 --> 0 | 0 |
按照前面的过程，我们取权值最小的边。这里最小的就是源节点本身，权值为0。然后，我们要遍历它所有邻接节点来判断是否有更短的路径。在这里，因为最开始初始化为它到其他节点的距离都是无穷大。于是我们相邻两个节点的距离实际上更近，需要更新节点１和２。于是我们得到如下图：
这个时候我们得到的边如下：
| 边 | 权值 |
| 0 --> 1 | 4 |
| 0 --> 2 | 10 |
对应的最短路径数组更新为：[0, 4, 10, INFINIT, INFINIT, INFINIT, INFINIT]。我们要注意到一点，每次取我们表里面最短的边之后，就将它从表里面移除。
我们再取里面里面最短的边0 -- > 1。 通过节点１再去比较更新它的邻接节点。此时，节点４的值需要被更新。于是有下图：
这个时候，对应的边如下：