如何在dijkstra算法的O（log n）时间中更新优先级队列中的密钥？

Question

在过去的一周中，我一直在研究dijkstra的算法，其中一个在Java中具有正确的运行代码。它使用数组来计算标准的findMin函数，该函数可以为您提供距离最小的顶点。显然它是O（n），现在我想使用Priority Queue（Min Heaps）来实现它

我的思考过程是：

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;
    }
  }
}

但是，如果堆中存在特定的顶点，则可以考虑找到的Min节点的距离来更新其距离。

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

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

在像我这样的幼稚实现中，它是O（n），

那么，谁能建议可以采取什么措施来解决这一瓶颈呢？我们如何在O（log n）时间中更新堆中的特定顶点？（类似地，我们如何在O（1）时间中找到特定元素）

Answer 1

我知道这种情况的两种基本方法：

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

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