怎么用python min heap 用于Dijkstra算法

Question

在这里输入代码

Answer 1

liuyubobobo 2019-08-08 10:20:19

在这个课程中提供的解法，是基于索引堆的哦。

索引堆在任何标准库中都不是现成的数据结构，所以，我们使用的是自己从底层实现的索引堆。具体索引堆的原理，在课程的第四章有详细介绍。

对于课程代码的 Python 实现，有很多同学已经完整地使用 Python 实现了课程的全部代码。在这里，我推荐以下两个同学的代码仓，供参考：

https://github.com/ShiveryMoon/Imooc-Algorithm-PythonEdition

https://github.com/nicemayi/play-with-algorithms

==========

关于只使用最小堆实现 Dijkstra 算法，我补充了一个代码（C++），传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/09-Shortest-Path/Course%20Code%20(C%2B%2B)/Optional-1-Dijkstra-based-on-Min-Heap/Dijkstra.h

关键点在于：

1）建立一个最小堆，最小堆中存储顶点，按照距离当前找到的和源点s的距离排序。（43-45行）

2）使用最小堆，而不是索引堆的核心区别在于，当修改distTo以后，最小堆里面的顶点排序不会变化。对此，解决方案是，我们但凡修改一个顶点的距离，就把这个顶点重新推入优先队列一次。在重新推入的过程中，这个顶点肯定会根据当前新计算出的距离，放在队列的正确位置。（73-76行）

3）但是，这样做，队列中就会有重复元素。所以，在while循环中，对于已经计算的元素，忽略掉。（55-56行）

继续加油！：）

• 提问者 慕仙0201785 #1

  优先队列怎么用于Dijkstra算法？

• liuyubobobo 回复 提问者 慕仙0201785 #2

  我在原答案下补充了一段代码和相关说明。加油！：）

• 提问者 慕仙0201785 回复 liuyubobobo #3

  谢谢，理解了