语言抽象,仅供自用。

证明一个即将加入S集合的点u必然D[u]=最小值min:

  假设D[u] != 最小值,那么即说明存在一条最短路径,该路径可以描述为:S集合中的一个点(至少为起始点)  +  一个任意点  ->  u。

现在假设此任意点在S集合内,因为此路径为最短路径,所以u也为最短路径上的组成点,所以u已经最优,和假设矛盾。

  又假设此任意点不在S集合内,因为无负边权,所以D[任意点] <= D[u],因为维护的是小顶堆,每次选出一个D值最小的加入S集合,所以下一个即将加入S的点应该是任意点。但是下一个要加入S的点应该是u,所以D[u] <= D[任意点],于是可以得出结论,u=任意点,也即下一个即将加入S的点。

  综上,即将加入S的点u已经最优。

05-08 15:33