1

对于分配，我需要使用实现为最小堆的优先级队列来实现 Dijkstra 算法。我已经有一个实现，其中我使用距离表和未处理顶点的无序数组。（如此处页面底部所述）。

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

3
1 2 3
3 2 1
1 3 1

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

谁能指出我正确的方向？

4

1 回答 1

0

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

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

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

对于不是荒谬密集的图，这会使优先级队列保持较小。

希望这可以帮助！

于 2013-05-08T02:53:53.387 回答