前言 在讲解优先队列 BFS 之前，让我们回顾一下最普通的走迷宫问题： 对于一个迷宫，从起点开始，对于四周能扩展的点打上标记并加入队列。直到从队列取出来的点表示的位置为终点时，退出搜索 显然，在没有限制的情况下，我们只需要给出一条路径，如果把迷宫看成一个无向图，那么每一条边其实都是边权为一的无向边。但我们如果给每一条边不同的权值，一般的 BFS 就不能解决这个问题了，因为它会在找到一条路径时立刻退出，不能保证最短路径被扩展。实际上这种问题我们可以通过最短路算法求解，而今天我们则尝试用优先队列 BFS 进行求解。…