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使得路径减小。不知道讲得清楚不清楚。