假设地图中存在起点和终点，路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划，或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法，和 Dijkstra 算法相比，A* 采用启发式的搜索策略，能够更快地搜索出最短路径。

1.前言

图中的起点和终点

给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图，有很多条路径可以从起点到达终点，但是很多不是最短路径。如上图所示，黑色虚线为最短路径，红色虚线不是。

Dijkstra 算法是其中一种求解起点到终点最短路径的算法，在用于无权重图时，Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化，引入启发式的搜索策略，可以更快地搜索出最短路径。

2.Dijkstra算法

假设起点是 s，终点是 e，Dijkstra 算法的主要包括下面的流程。

• 步骤一：用一个集合 F 保存已经访问过的节点，初始时 F 只包含起点 s。用一个数组 D 保存起点 s