首先证明那个比较显然的推论
我们先证明一下一个小引理：这个BFS先出队的点一定比后出队的点的代价小或等于
用数学归纳法，假设前面已经出队的点满足以上性质，之前最后一个出队的点为\(x\)，现在队列里面的队首是\(y\)，那我们就是要证明\(y\)的代价比\(x\)小或等于
我们考虑一下\(y\)是怎么来的
如果\(y\)是由\(x\)扩展来的，那么由于边权非负，所以结论得证
如果\(y\)不是由\(x\)扩展而来的，那么之所以\(y\)比\(x\)后出队，就是因为\(y\)的代价大于等于\(x\)，所以结论也得证
由以上证明不难得出，其实优先队列的BFS都满足这个引理
然后我们考虑反证，假设\(x\)这个点已经第\(i\)次被取出了，由以上推论那么这一条路径显然至少是第\(i\)短路
如果这条路径不是第\(i\)短路，那么我直接让这个队列扩展无穷次，第\(i\)短路一定会出现，而且出现在这一条路径的后面
与推论矛盾，所以蓝书推论得证
然后我们考虑用A*优化这一个优先队列BFS，估价函数就像蓝书这么设计
很巧的一件事情是，这么设计后，不会出现上一篇博客说的那种特殊情况，就是仍然满足P126说的这个推论
我们考虑一下什么BFS才满足我们上面证明的引理：搜索树上的边权非负
那么这个A*的边权非负吗？是的
考虑搜索树上的一个点\(x\)，有一条边\((x,y,w)\)，其中\(w\)是边权
由最短路定义可得\(f_{x}≤f_{y}+w\)
所以\(dist+f_{x}≤dist+w+f_{y}\)
而上式前者是\(x\)的代价，后者是\(y\)的代价
所以边权非负，也满足这个引理
然后对同一个点取出了\(i\)次，那么第\(i\)次一定是第\(i\)短路，因为对于同一个点估价函数是相同的，不同的实际代价，也就是第\(i\)短路
标签：推论,解释,非负,短路,BFS,出队,一题,边权 From： https://www.cnblogs.com/dingxingdi/p/17851940.html