一、问题背景
在游戏寻路、地图导航等场景中，我们需要在巨大地图中快速找到一条接近最短的路线。
- Dijkstra 算法能保证最短路径，但搜索方向"盲目"，在超大图上效率低
- 实际应用中，往往不需要绝对最短，只需次优但足够快
A* 算法就是对 Dijkstra 的启发式改进：引入"终点方向估计"，让搜索不再跑偏。
二、从 Dijkstra 到 A*
2.1 Dijkstra 的"跑偏"问题
Dijkstra 按 g(i)（起点到当前点的实际距离）选择下一个扩展点。在地图场景中，这导致搜索可能朝远离终点的方向扩展。
Mermaid · 渲染中（下方为源码）
graph LR S((S)) -->|1| A((1)) A -->|1| B((2)) B -->|1| C((3)) S -->|4| D((4)) D -->|1| T((T))
上图中，Dijkstra 会先扩展 1→2→3（离 S 近），但终点 T 在另一侧。
2.2 A* 的改进：引入启发函数
A* 综合考虑两个因素：
| 符号 | 含义 |
|---|---|
| g(i) | 起点到顶点 i 的实际路径长度 |
| h(i) | 顶点 i 到终点的估计距离（启发函数） |
| f(i) = g(i) + h(i) | 估价函数，决定扩展优先级 |
每次从优先队列中取 f 值最小的顶点扩展，搜索方向被"拉向"终点。