1回答

liuyubobobo

2019-08-08

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

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

对于课程代码的 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行）

继续加油！：）

0

3

慕仙0201785

回复

liuyubobobo

谢谢，理解了

2019-08-09

共3条回复