路径规划算法1.2图搜索算法——广度优先搜索、Dijkstra与A*寻路算法

前言

路径规划算法1.1给出了早期的图搜索算法，可视图法（VG）。本次记录基于图搜索的两种经典寻路算法Dijkstra和A*，这两个算法深刻影响了后续的grid-based算法。

这里会借助Red Blob Games主页进行叙述。

广度优先搜索

这里又提到了广度优先搜索方法，这个概念是图论中引出的。BFS的意思就是对于图（树）上的每一个节点都要展开，并且在每个方向上的展开优先级都是一致的，每个被遍历的节点都能得到其连接信息。

以上就是从遍历全图的过程：

• 将起点放入先进先出列表Q中。
• 取出Q中的节点（刚开始就是起点）。
• 访问该节点的所有邻接节点并放入Q中，（已经加入队列的节点不能再被访问），然后该节点展开完成。
• 取出下一个节点，重复以上过程，直到没有节点再能被展开后结束。

在节点展开的过程中，如果记录下每个节点与它访问到的节点，就形成了节点之间的路径：

作为寻路算法时，不需要将所有节点都展开，当目标节点被搜索到时就可以提前结束了： （图源 Red Blob Games）

Dijkstra算法 有权图Dijkstra算法

Dijkstra是一种广度优先搜索算法（Breadth-First Search, BFS），不过该Dijkstra在搜索中引入了从起点到节点的cost作为引导，因此能够在有权图中获得到达每个路点最短的路径。

对于以上这个有权图，以A为起点，算法的流程是这样的：

1. 建立两个队列U（记录已到达节点）、Q（未到达节点），以及一个数组array（记录从起点到其他各点的最短距离）。
2. 初始化U={A}、Q={B,C,D,E,F}、array={5,10,15,inf,inf}（如果起点不能到达某节点，则距离记为inf）
3. 提取Q中与A距离最近的节点s，把s放入U
4. 更新array中的最短距离
5. 循环3、4步骤

具体流程就是： array中AB距离最小，从Q中取出B放入U={A,B}，BE相连，array中A->B->E的距离=13C->D的距离14B->E->D的距离=14=14，A->B->E->F的距离=22B->E->D-F的距离=20