~ 题干 ~
从A点到G点，哪一条路径才是最短的？最短是多少？
这是一个经典的图类型的算法，在实际生活中也有广泛的应用，例如：我们在地图软件上搜索从某地到某地如何去时，地图软件会很快的帮我们找出最适合的路径。（当然地图软件考虑的因素更多）
但是主要核心就是求一个 “图” 中两点之间加权的最优路径问题。
~ 算法理解 ~
对于 “图” 中两点最优路径问题，已有很多种现成的算法，这次我们用 “迪杰斯特拉（dijkstra）” 算法来解题。
网上随便一搜就可以搜到很多 “迪杰斯特拉” 算法的讲解，但是真正能讲透的不多。
算法最难的地方不是过程，而是思想。很多讲 “迪杰斯特拉” 算法的文章都只是告诉你，算法应该如何如何写，但是都没有讲清楚为什么要这么设计算法，为什么这么设计是对的。
下面按照迪杰斯特拉算法一步一步来讲解，并且尽量解释清楚为什么算法要这么做：
1. 选取一个起点（A），其他所有的点到（A）的距离都为无穷（∞），表示初始还未计算时，所有的点到（A）都不可达。但是（A）自身是0。并且把所有的点包括（A）自己都放入一个集合（S），（S）表示待确定的节点（后面通过算法一步一步会把待确定的点变确定）。
用下表表示：
节点 | 当前到A点的最短距离 |
A | 0 |
B | ∞ |
C | ∞ |
D | ∞ |
E | ∞ |
F | ∞ |
G | ∞ |
H | ∞ |
2. 从待确定的节点集合（S）中，选出距离（A）点最近的点，因为（A）点距离（A）点是0，其他都是∞，所以（A）点首先被确定，从（S）中去除（A）点。确定的点我们用绿色表示：
节点 | 当前到A点的最短距离 |
A | 0 |
B | ∞ |
C | ∞ |
D | ∞ |
E | ∞ |
F | ∞ |
G | ∞ |
H | ∞ |
3. 找到从（A）直接可达的节点，比较这些节点到（A）的距离和当前到A点的最短距离哪个短，取较短的那个更新。表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5（5比∞小，所以更新为5） |
C | ∞ |
D | ∞ |
E | ∞ |
F | 3（3比∞小，所以更新为3） |
G | ∞ |
H | ∞ |
此时虽然（B）和（F）更新了到（A）点的距离，但是，并不能说（A）到（B）最短就是5了，因为有可能从别的路绕一圈更近。所以这个时候绿框还是只有（A）
4. 重复步骤2：从待确定的节点集合（S）中，选出距离（A）点最近的点。注意：待确定的节点集合其实就是没有标绿色的那些节点。
这个时候，（S）中距离（A）最短的是3，也就是（F）点，（F）点可以从待确定集合（S）中去除，变为确定节点。
为什么（S）中距离（A）最短的就可以确定？这是很多文章都忽略了的一个关键点：因为距离（A）最短的这个节点，是不可能存在其他弯弯绕的路径比他更短了，因为其他的直接路径已经比他长了，再绕路就会更长！用下图来说明：
为什么（F）可以变为绿色？因为从（A）到（F）的最短距离一定是3，不可能从（B）绕圈绕到（F）比3还短，因为（A）到（B）已经比3大了。
那为啥（B）不能变绿，因为无法确定从（A）直接到（B）就是最短路径，他有可能从（F）绕一圈到（B）比5更小呢。
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5（5比∞小，所以更新为5） |
C | ∞ |
D | ∞ |
E | ∞ |
F | 3 |
G | ∞ |
H | ∞ |
5. 重复步骤3，因为（F）到（A）的最短距离已经确定了，从（F）出发能到达的节点 到（A）的最短距离就可以更新了。
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | ∞ |
D | ∞ |
E | 5（F + 2比∞小，所以更新为F + 2 = 5） |
F | 3 |
G | 10（F + 7比∞小，所以更新为F + 7 = 10） |
H | 5（F + 2比∞小，所以更新为F + 2 = 5） |
6. 重复步骤2：确定下一个变绿的节点，发现有2个节点都是2，我们可以把2个节点都变绿。这表示（E）和（H）都是可以确定下来的节点。
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | ∞ |
D | ∞ |
E | 5 |
F | 3 |
G | 10 |
H | 5 |
7. 重复步骤3，把新增的（E）和（H）能到达的直接节点的值更新
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | ∞ |
D | ∞ |
E | 5 |
F | 3 |
G | 8（H + 3 < 10, 所以更新为8） |
H | 5 |
8. 重复步骤2
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | ∞ |
D | ∞ |
E | 5 |
F | 3 |
G | 8（H + 3 < 10, 所以更新为8） |
H | 5 |
9. 重复步骤3
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | 7（B + 2 < ∞，更新为B + 2） |
D | ∞ |
E | 5（已经变绿，不需要再计算） |
F | 3 |
G | 8（H + 3 < 10, 所以更新为8） |
H | 5 |
10. 重复步骤2，（C）变绿
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | 7 |
D | ∞ |
E | 5 |
F | 3 |
G | 8 |
H | 5 |
11. 重复步骤3
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | 7 |
D | 11（C + 4 < ∞，取C + 4） |
E | 5 |
F | 3 |
G | 8 |
H | 5 |
12. 重复步骤2，（G）变绿，此时已经达到了我们的目的，找到了从（A）到（G）的最短路径。为了完整，我们把最后的（D）也计算出来。
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | 7 |
D | 11（C + 4 < ∞，取C + 4） |
E | 5 |
F | 3 |
G | 8 |
H | 5 |
13. 重复步骤3和2，最后表格中所有的行都变绿，也就计算出了从（A）点到所有其他点的最短路径。
表变为如下：
节点 | 当前到A点的最短距离 |
A | 0 |
B | 5 |
C | 7 |
D | 11 |
E | 5 |
F | 3 |
G | 8 |
H | 5 |
~ 总结 ~
看上去迪杰斯特拉算法挺复杂的，其实只有2步，不断的重复步骤2和步骤3。
关键点是要理解为什么从未确定节点集合（S）中拿出最小值的节点，就可以作为确定节点，想通了这一点，整个迪杰斯特拉算法就一目了然非常清晰了。