在过去的一周里,我一直在研究 dijkstra 的算法,我在 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) 时间内找到特定元素)
最佳答案
我知道针对这种情况的两种基本方法:
每当您访问顶点的邻居时,无论它们是否在堆中,都将它们插入堆中。然后,当你得到离堆最小距离的顶点时,检查它是否已经从堆中移除。如果有,则也将其删除并继续。否则,将其标记为已移除并访问所有邻居。
保留指向堆中每个元素所在位置的显式指针。然后,您可以对已定位的元素执行称为“减少键”的操作。
关于algorithm - 如何在 dijkstra 算法中以 O(log n ) 时间更新优先级队列中的 key ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11802333/