c - 使用 Dijkstra 算法的有向图的优先级队列/最小堆

Question

对于一项作业，我需要使用实现为最小堆的优先级队列来实现 Dijkstra 算法。我已经有了一个使用距离表和未处理顶点的无序数组的实现。 (如页面底部所述 here )。

下面给出了一个示例输入文件，其中第一行是顶点数，后面的每一行是:源、目标、权重。

3
1 2 3
3 2 1
1 3 1

我最初的想法是将图中的每条边都视为堆中的一个节点，但这是不对的，因为其中一个测试文件有 15677372 条边，如果没有立即生成一个那么大的数组，我什至做不到段错误。在使用未处理的顶点数组实现该方法后，似乎我需要以某种方式用堆替换该数组，但我不确定该怎么做。

谁能指出我正确的方向？

Answer 1

通常，在 Dijkstra 算法中，您的优先级队列将保存图中的节点以及到目前为止到该节点的最佳估计距离。标准技术是将图中的所有节点最初以距离∞入队到优先级队列中，然后使用队列的减少键操作根据需要降低它们。

从内存的角度来看，这通常是完全不可行的，因此另一种解释是最初保持队列为空，然后用距离为 0 的起始节点为它播种。每次处理一个节点，然后更新距离估计它的每个相邻节点。您可以按如下方式执行此操作:

• 如果节点已经在优先级队列中，可以使用decrease-key来降低节点的距离。
• 如果该节点尚未在优先级队列中，则以所需的优先级将其插入。

这使得优先级队列对于非密集的图表保持较小。

希望这对您有所帮助!