A* 又称启发式搜索，能够解决带权有向图上的最短路问题。具体的，给出起点 s 和终点 t，它能在不劣于（不是一定优于）优先队列 bfs（即 Dijkstra）的时间内求出从起点到终点的最短路。
我们先来思考，为什么 Dijkstra 会在有些情况下慢呢？因为它的优先队列只保证了 s 到队头点的距离最短，但如果队头到 t 的最短路不是最优解，而队尾点到 t 是最优解，那么就会花费大量时间使用优先队列前面的点松弛，松弛出来的也不是最优解。A* 就解决了这个问题，它保证了在优先队列中靠前的点 u 从 s 到 u 再到 t 的路径一定是比较优的。
具体的，对于每个点 x 都有两个属性 g(x),h(x)，其中 g(x) 为起点到当前节点的最短路（由前驱点松弛得到），h(x) 为 x 的预估价值，在最短路问题中就是预估的 x 到 t 的最短路。定义 x 点的价值 f(x)=g(x)+h(x)，优先队列中的节点按价值 f 排序。
可以发现，当 h(x)=0 时，一个点的价值就相当于起点到当前点的最短路，这时算法就退化为了 Dijkstra。这启示我们，恰当的 h 函数值可以让 A* 算法的复杂度降低。需要特别注意的是，h 预估的值必须是最乐观的估计，即只能估少不能估多。具体证明可以看这篇文章。sto
稍微总结一下，Dijkstra 只是保证了 s 到队头 u 最优，而 A* 虽然没有保证它，但它保证了 s 到 u 再到 t 是最优的。
例题
A* 算法最重要的就是 h 函数的设计。
走迷宫
题目
给出一个 n \times m 的迷宫，每单位时间内可以从一个点向四个方向走一步求从 (1,1) 到 (n,m) 最少需要多少单位时间。
解析
显然 dfs 和 bfs 可做。这里给出 A* 做法。
显然 f(x,y) 可以
踩蛋
:::warning
不知道大家发现了没有，想要用 A* 求最短路前，为了得到每个点的 h 函数，必须知道当前点到终点 t 的最短路，需要建反图跑 Dijkstra。这样就不如我们直接跑一遍 Dijkstra 了。