Dijkstra 和 A* 最短路径

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

如果每个区块的移动成本不同，仅靠简单的 BFS 无法保证最便宜的路线。 这时候就用到了Dijkstra、A*等最短路径算法。

Dijkstra

从起点到现在累计成本最低的顶点首先进行扩展。

新成本 = 当前成本 + 下一干线成本

如果新的成本低于旧的记录
更新距离和先前的顶点。

使用优先级队列时，一般O((V + E) log V)可以执行到这个程度。 不应使用默认的 Dijkstra，因为负边的存在可能会减少已建立的最短距离。

A*

A* 是从起点算起的实际成本g以及达到目标的预计成本。h添加以确定优先级。

f(n) = g(n) + h(n)

在网格中，曼哈顿距离或欧几里得距离可以用作启发式。 对于六角网格，必须使用适合六角坐标的距离函数。

如果估计成本没有高估实际的最低剩余成本，则可以保证最短路径。 如果 Heuristic 为 0，A* 的行为类似于 Dijkstra。

使用哪一个？

需要从一个起点出发的多个目的地成本：Dijkstra
快速导航至一个目的地：A*
所有中继成本相同：BFS

路径搜索性能不仅仅由算法名称决定。 还必须检查邻居生成成本、障碍物表示、优先级队列和启发式质量。