Dijkstra

迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是 next 点)递增次序产生最短路径。先把 V 分成两组：

• S：已求出最短路径的顶点的集合
• V-S=T：尚未确定最短路径的顶点集合

将 T 中顶点按最短路径递增的次序加入到 S 中，依据：可以证明 V0 到 T 中顶点 Vk 的最短路径，或是从 V0 到 Vk 的直接路径的权值或是从 V0 经 S 中顶点到 Vk 的路径权值之和。求最短路径的步骤如下:

• 初使时令 S={V0},T={其余顶点}，T 中顶点对应的距离值，若存在<V0,Vi>，为<V0,Vi>弧上的权值(和ＳＰＦＡ初始化方式不同)，若不存在<V0,Vi>，为 Inf。

• 从 T 中选取一个其距离值为最小的顶点 W(贪心体现在此处)，加入 S(注意不是直接从 S 集合中选取，理解这个对于理解 vis 数组的作用至关重要)，对 T 中顶点的距离值进行修改：若加进 W 作中间顶点，从 V0 到 Vi 的距离值比不加 W 的路径要短，则修改此距离值(上面两个并列 for 循环，使用最小点更新)。

• 重复上述步骤，直到 S 中包含所有顶点，即 S=V 为止(说明最外层是除起点外的遍历)。

Dijkstra 算法的缺陷之一是不能处理负权边，这与贪心选择性质有关，每次都找一个距源点最近的点(dmin)，然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点(dmin’)，再通过这个负权边 L(L<0)，使得路径之和更小(dmin’+L<dmin),则 dmin’+L 成为最短路径，并不是 dmin，这样 dijkstra 就被囧掉了。比如 n=3，邻接矩阵：

0，3，4
3，0，-2
4，-2，0,

用 dijkstra 求得 d[1，2]=3，事实上 d[1，2]=2，就是通过了 1-3-2 使得路径减小。不知道讲得清楚不清楚。