过去一周我一直在研究 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) 时间内找到特定元素)
我知道针对这种情况有两种基本方法:
每当您访问顶点的邻居时,无论它们是否在堆中,都将它们插入堆中。然后,当你得到距堆最小距离的顶点时,检查它是否已经从堆中删除。如果有,请将其也删除并继续。否则,将其标记为已删除并访问所有邻居。
保留一个明确的指针,指向每个元素在堆中的位置。然后,您可以对已找到的元素执行称为“减少键”的操作。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)