Dijkstra正确性证明

采用反证法+数学归纳法

设目前已经出对的点得到的都是最短路，那么对于现在刚好出队这个点t来说：

1. 因为它是优先队列的对头，而且图中的边权都是非负数，所以它不可能被队列中的点再更新
2. 因为每个点只会出队一次，所以它也不会被已经出队的点再次更新
3. 还没有入队的点距离更远，也不可能再更新它

综上，每个点的最短路距离在出队时就已经确定了。

A*实现的K短路正确性证明

首先，设每个点的估价总距离为h(x)，实际总距离为a(x)，当前求出的距离为s(x)，估价函数为f(x)

1.

对于路径u1->u2->u3->...->un来说，如果我们正处在求k短路的迭代过程当中，那么其中的任何一个字段，都不可能包含i短路(i>k)的部分：

反证法：假设它包含，那么这一段就可以被替换为更短的子段，与我们的前提矛盾。

因此，对于每个点，当它的遍历次数达到k时，就可以无视它了

2.

对于满足拓扑序的一段路径，u1->u2->...->un来说，h(ui)非严格递增。

 只有在最理想的情况下，对于j>i，才会有h(j)=h(i)，其他情况下h(j)>h(i)，所以h(j)>=h(i)

3.

最重要的一部分

重点第i次出队时，得到的就是第i短路。

可以采用归纳法证明：

第一次出队时，假设得到的这个dist1大于最优值dis1，那么

1.若当前优先队列中有最优路径上的点u，则dist1>dis1>=h(u)，与当前点时优先队列队友矛盾。

2.若当前队列中没有最优路径上的点，只有已经出队的点中包含了最优路径上的点，那就需要先从当前队列点绕到那些已经出队的点，再把它入队来更新最优值，因为只有非负权边，显然会越找越大。

以此类推....

证毕。