algorithm - 如何更新 Dijkstra 算法中松弛顶点的 key ？

Question

就像被问到的一样here ,我不明白我们如何在堆中找到松弛顶点的索引。

在编程风格方面，堆 是一个抽象出优先级队列细节的黑盒子。现在，如果我们需要维护一个将顶点键映射到堆数组中相应索引的哈希表，那将需要在 heap 实现中完成，对吗？

但是大多数标准堆不提供进行此类映射的哈希表。

另一种处理整个问题的方法是不管任何事情都将松弛顶点添加到堆中。当我们提取最小值时，我们将得到最好的。为了防止同一顶点被多次提取，我们可以将其标记为已访问。

所以我的确切问题是，处理此问题的典型方法是什么？

与我提到的方法相比，优缺点是什么？

Answer 1

通常，您需要一个支持 decreaseKey 操作的特殊构造的优先级队列才能使其正常工作。我已经看到这是通过让优先级队列显式跟踪索引的哈希表(如果使用二叉堆)，或者通过具有侵入式优先级队列实现的，其中存储的元素是堆中的节点(如果使用二项式堆)或斐波那契堆，例如)。有时，优先级队列的插入操作会返回一个指向优先级队列中持有新增键的节点的指针。例如，这是一个 implementation of a Fibonacci heap支持 decreaseKey。它的工作原理是让每个插入操作返回一个指向 Fibonacci 堆中节点的指针，这使得在 O(1) 中查找节点成为可能，假设您跟踪返回的指针。

希望这对您有所帮助!