dijkstra算法的证明

缘起

RT.

分析

dijkstra很多人会敲，而且网上板子也很多，但是dijkstra算法的证明网上很多都不大严格. 本文给出一种简单的、正确的证明.

关键是意识到, S是一个集合，伊始只有单源，然后算法每次循环做的事情其实是先选出”仅仅经过集合S中的点到达单源距离最短的而且尚未在S中的点”，然后将其加入S，并且利用它来松弛其他尚未在S中的点仅仅通过S中的点抵达单源的最短距离.

即算法每次循环首先选出
$$
min_{u\notin S}{ 单源出发仅仅经过S中的点抵达u的路径的长度 }
$$
中的u

我们意识到dijkstra是做这件事情之后，就好证明为什么每次循环先选出的点（记做u）就已经是它到达单源最短路径了. 反证法，因为我们目前求出的距离是u到达单源仅仅经过S中的点能达到的最短距离. 如果最短路径另有其他的话，则一定是经过了尚未在S中的点. 即存在这样的路径（记做P）

S中的点（至少包括单源）–>一系列不在S中的点（至少包含一个点,记第一个为y）–>u

它才是从单源到u的最短路径. 但是y仅仅经过S到达单源的距离>=u仅仅经过S到达单源的距离（因为此时y尚未出堆，u是此时出堆的）. 更何况y还需要经历一些点到达u, 所以P的长度>=u仅仅经过S到达单源的距离.

所以这就证明了dijkstra算法的正确性.

上面的论述其实换成一张图就是

黄色的①>=黑色的②，所以黄色的①+黑色的③更>=黑色的②了

所以根本不可能还经过一个尚未加入S的y（!=u）到达u的路径成为最短的.