迪杰斯特拉算法的理解

图片转载自：最短路径算法-迪杰斯特拉(Dijkstra)算法 - 程序小哥爱读书的文章 - 知乎
https://zhuanlan.zhihu.com/p/346558578
迪杰斯特拉，一个广度优先算法，采用了贪心策略。

第一步，选取顶点D，更新和D相连的节点C，E

第二步，选取顶点C，因为和D直接相连的就只有C，D，他俩之中必然有一个是最短的，而且此时C到D的最短路径已经确定了，为什么？因为不可能存在另一个节点X能连接D和C了，所以C是确定了的，那么，我们再以C来更新别的，更新和C相连的，发现能更新B，F，E不能更新，从D到E的已经最短了。

第三步，选出E，为什么能确定E是最短的，因为现在E的最短路径，是从S集合里的每一个点更新而来的，不可能存在一个点在D和E之间，如果有，早就被加到S中去了，所以E一定是最短的。E可以加入S中，并且以E来更新新的节点，能更新F和G。这里我么发现，D->C->F这条路径会被pass，改成D->E->F，这说明，每次更新都是用已经确定了最短路径的元素来更新的，当前的F，其实已经被比了两次了！

我们发现，每次更新，都是以这个已经确定了最短路径的点来更新，更新完之后，再在U里挑一个最短的节点u加入S，为什么能确定此时u就是最短的，并且不会再更新呢？

1. u 到起点的最短路径只能通过集合 S中的节点，因为在之前的步骤中，所有在 S 中的节点已经被处理过，它们的最短路径已经确定。
2. 由于 u 是当前距离起点最近的未处理节点，意味着无论通过哪个已处理节点（属于 S），也不会有比当前路径更短的路径到达 u。因为都和F一样，被比过了。
3. 如果有更短的路径到达 u，那么该路径一定经过一个还未处理的节点x（属于 U）。但是，这与选择 u 为当前最近的未处理节点相矛盾。因此，不可能存在这样一条更短的路径。（假如有x更短并且还在U中，我们就不会选u)