Question

为什么Dijkstra算法是正确的

Answer 1

首先，咱们知道，dijkstra算法是不能应用于有负权边的图中的。

为什么呢？
就因为这个算法事实上是一个贪心。

从第一步开始，假设第一个节点是u，那么第一次会拓展所有相邻节点
然后会找到与它相邻的点中最近的那个，设为v1。
因为我们假设了没有负权，所以可以肯定，u-v1的最短距离一定是(u,v1)这条边。因为如果不是走(u,v1)，从u出发势必要走另一条(u,v2)，而因为(u,v1)是最短的，所以有(u,v2)>=(u,v1),则(u,v2)+cost(v2,v1)>(u,v1)。
这样的一步就比较明显的看出了这个算法的本质，每次选出通过能到达的点中更新出的最短节点，那么这个距离一定是最短距离。
不然还是必须要通过另一个已经到达的节点[不然就不可能到达了]，而到达那个节点的代价一定大于这个已走点中最短的一个。

所以每一步都选出一个确定正确的点，通过它再一次更新可以到达的范围，这样下去直到拓展到目标点都是正确的。