如何在Dijkstra算法中以O(log n)的时间更新优先队列中的关键字？

Question

过去一周我一直在研究迪杰斯特拉算法，现在我已经用Java编写了正确运行的代码。它使用数组计算标准findMin函数，该函数会返回距离最近的顶点，显然这个方法是O(n)。现在我想使用优先队列（最小堆）来实现它。

我的思路是：

while (there are unseen Vertex)
{

    vertex= get TheVertex WithSmallest Distance Yet;//(In can be done in O(log n) using heap)

  for this vertex {

    find all of the adjacent edges and traverse them.

    for a particular vertex which is not there in heap yet{

        Simply add it in the queue;
    }
  }
}

如果一个特定的顶点存在于堆中，则可以考虑将其距离更新为找到的最小节点的距离。

现在我的问题是如何在O（log n）时间内更新堆中的特定元素。

我们不能在O（1）时间内找到该元素，对吧？

在我这样的天真实现中，它可能需要 O(n) 时间,

那么有人能建议如何处理这种瓶颈吗？如何在O(log n)时间内更新堆中的特定顶点？（类似地，如何在O(1)时间内找到特定元素）

- Max

Answer 1

我知道有两种基本方法可以解决这个问题：

1. 每当你访问一个顶点的相邻节点时，无论它们是否在堆中，都将它们插入堆中。然后，当你从堆中得到距离最小的顶点时，请检查它以前是否已经从堆中删除过。如果是，则也要将其删除并继续。否则，标记它为已删除并访问所有邻居。

2. 保持对堆中每个元素所在位置的显式指针。然后，可以对已定位的元素执行称为“减少键”的操作。

- Ivan Vergiliev

---

请注意，第一种方法将使总运行时间为 O((E + V) * log (E))，因为PQ中现在最多可能有O(E)个元素。 - bigfoot

Log(E)在大O符号中仍然与log(V)相同。除非图是多重图，否则E <= V ^ 2。因此，log(E) = log(V ^ 2) = 2log(V)，所以它只是一个常数因子的差异。 - Ivan Vergiliev