dijkstra 算法的重点是理解算法正确性成立的条件。

dijkstra 算法有一个正确性的前提条件，就是边权不能为 负。
原因是：算法的正确性证明里面，用了这个条件。一旦条件不满足，算法的正确性就塌了。

dijkstra 努力维护一个“已经获得从起点出发最距离的点的集合 S”。
最开始把起点 "小 s" 加入到集合 "大 S" 里面。
然后不断的从 S 外找到 “还没有加入 S 的，距离起点最短的点”，然后把它加入 S。
这个找候选点的第一步，就是把 S 中唯一的一个点 s 直接相连的点加入“候选集合”。
然后不断从 “候选集合”中找到距离 s 最短的点，把它加入 S。
这个点加入 S 的同时，枚举与它直接连接的点，更新（松弛）这些点到 s 的距离。
一旦某个点的距离被松弛，则加入到“候选集合”中。
同一个点如果被多次松弛，则有可能多次被加入“候选集和”。

上述“把候选集合中距离 s 最小的点加入 S”这个步骤，需要证明这时候这个点与 s 的距离已经是最短路，
不可能再被更新了。
这个关键环节用到了“边权不能为负”的条件。
具体证明有点复杂，我勉强能看懂，自己写出来有困难。您可以参考《算法导论》。



【 在 DorD 的大作中提到: 】
: 真没想到，还能在认知上提升，非常感谢！因为我以前根本就不知道这篇论文，或者说我学的层次还没有达到那个境界。
: 我写了一段对dijkstra算法的理解，麻烦您再看一下。
: 1，与起点有直接相连的，距离记录在数组中。没有直连的，记为无穷大。
: ...................
--
FROM 223.72.44.*