《Python编程从0到1 视频教学版》_深入Python设计的本质_3.6.2 Dijkstra 算法

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第6节，作者是张頔。

3.6.2 Dijkstra 算法

Dijkstra 算法用于在有权图中寻找最短路径。该算法是其他许多图搜索算法的基础。 算法描述如下：

(1)将所有节点标记为“未访问”。将出发节点距离设置为0,其他节点的“临时距 离"设置为无穷大；

(2)在"未访问”节点集合中选取距离值最小的节点C, 更新其相邻节点的“临时距 离"。更新方法：如果C 的距离值与C 到该节点的距离之和 sum 小于该节点当前距离值， 则更新该节点距离值为sum; 否则，保持该节点距离值不变(直观地说，就是看看C 周围 的节点可否经由C 获得比之前搜索结果更短的路径);

(3)将C 的状态设置为“已访问” (不会再有更短的到达C 的路径了);

(4)如果还有"未访问"节点，则返回第(2)步。如果全部节点均“已访问”,则 结束扫描，此时各节点标记距离即为从出发点到该节点的最短距离；

(5)根据各节点的距离值，从任意目标节点反向求出至起始节点的路径。

【思考和扩展练习】

(1)如何表示本小节展示的带有地形的格点地图?

(2)编写程序，实现在该地图中寻路的 Dijkstra 算法。

(3)不使用能够加速寻找最小距离值的结构， Dijkstra 算法的时间复杂度是怎样的(提示和节点数V 与边数E 均有关系)?

(4)如何使用优先队列优化 Dijkstra算法?优化得到的时间复杂度是怎样的[23]?

(5)如果事先知道目标节点，算法可以在什么情况下提前终止?

(6)如何处理图不连通的情况?

(7)Dijkstra算法与广度优先搜索算法有什么区别和联系?

(8)使用广度优先搜索求解有地形地图最短路径，会得到什么结果?

3.6.3 A*算法

为了学习A* 算法，需要首先回顾一下Dijkstra算法，并且理解将后者应用于地图寻路 问题时的性能。简单、直观地概括Dijkstra算法就是：向各个方向探路，优先处理较近的 节点，不断更新到达各节点的最短距离。 Dijkstra 算法用于地图寻路时的核心行为特征是 “在遇到阻力较大的路径时绕过去”,如图3.58所示。

然而，单纯地使用Dijkstra 算法在地图中寻路是低效的。日常生活中，在地图上的道 路网络上寻径都是先按照某个大致方向寻找，以避免“南辕北辙”,如图3.59所示。

Dijkstra 算法始终在前沿节点集合中，挑选从出发节点开始距离代价较短的节点，再 行探路。 A* 算法则把目标方位的因素考虑在内，其关键在于，将出发节点开始的距离代价 与对终点距离的估计之和，作为挑选下一个探路节点的依据。

A*算法的发明人 Peter E.Hart在1968年的论文[22]中写下了这样一段话： “为了在 搜索最优路径上探寻最少可能的节点，搜索算法必须持续决策下一个探路节点。在明显非最优路径节点的探路工作就是浪费时间。反之，如果忽视可能的最优路径节点则会导致无 法求得期望的结果。 一个有效的算法需要某种对节点的评价方法以确定探路方向。”

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。