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

Question

我一直在研究过去一周的dijkstra算法，我在java中拥有正确的运行代码。它使用数组来计算标准findMin函数，它为您提供最小距离的顶点。显然它是O（n），现在我正在使用优先级队列（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; 
    } 
    } 
} 

但是，如果在堆中存在一个特定的顶点，然后它的距离可能会考虑到发现闵节点的距离进行更新。

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

我们无法在O（1）中找到这个元素的时间正确吗？

在我幼稚的做法像我这是为O（n），

所以任何人可以建议可以做些什么来处理这个瓶颈？我们如何在O（log n）时间更新Heap中的特定顶点？ （同样，我们如何才能找到在O（1）时间的特定元素）

Answer 1

我所知，这种情况下两种基本方法：

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

2. 保留一个显式指针，指向堆中每个元素的位置。然后，您可以在已经找到的元素上执行称为“减少键”的操作。