《算法的乐趣》第六十四节

本节介绍Dijkstra算法的实现与A*算法原理。Dijkstra算法维护已确定最短路径的集合S和待处理集合Q，每次从Q中取出距离最小的顶点移入S，并用它松弛相连顶点的距离……

本节介绍Dijkstra算法的实现与A*算法原理。Dijkstra算法维护已确定最短路径的集合S和待处理集合Q，每次从Q中取出距离最小的顶点移入S，并用它松弛相连顶点的距离，直至Q为空；记录前驱顶点可回溯路径。演示显示其在无障碍地图上层层向外搜索，有障碍时几乎搜遍全图。为提高效率引入启发式搜索，利用评估函数选择、排序或剪枝。BFS算法只看与终点的距离，有障碍时往往得不到最短路径。A*算法将二者结合，评估函数F(n)=G(n)+H(n)，G(n)为起点到当前点的实际代价，H(n)为到终点的估计值；G取0近似BFS，H取0退化为Dijkstra。算法用OPEN、CLOSE两表迭代，取F最小节点扩展邻居。H(n)可用曼哈顿距离、欧氏距离、切比雪夫距离等，无障碍时效果相同，有障碍时略有差异。