如何更新优先级队列的关键在O（log n）的时间，Dijkstra算法？ [英] how to Update a key in Priority Queue in O(log n ) time in dijkstra's algorithm?

问题描述

我一直在Dijkstra算法在过去一一星期，我已经在Java中正确运行code吧。它是利用阵列的标准findMin函数的计算，让你与distance.Obviously最小的顶点是O（n）和现在，我期待使用来实现它的优先级队列（最小堆）

I have been working on dijkstra's algorithm for the past one week one I have the correct running code for it in java. It is using array for the computation of standard findMin function which gives you the vertex with smallest distance.Obviously it is O(n) and Now I am looking to implement it using 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;
    }
  }
}

但是，如果一个特定顶点存在于堆那么它的距离可能被更新考虑到发现闵节点的距离。

But if a particular vertex exists in the heap then its distance might be updated taking into account the distance of the found Min node.

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

Now My question is How will be update a particular element in The Heap in O(log n )time.

我们无法找到为O的元件（1）的时间吧？

We cant find that element in O(1) time right?

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

in my naive implementation like mine it would be O(n),

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

So can any one suggest what can be done to handle this bottleneck? How can we update a particular vertex in the Heap in O(log n) time? (similarly how can we find a particular element in O(1) time )

推荐答案

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

I'm aware of two basic approaches for this situation:

1. 每当你访问一个顶点的邻居，不管他们是在堆或不将其插入堆。然后，当你从堆最小距离顶点，检查是否已经从堆中删除之前。如果是，那么删除这一个了，继续。否则，将其标记为删除，访问所有的邻国。

1. Whenever you're visiting the neighbors of a vertex, insert them in the heap no matter if they are in the heap or not. Then, when you get the vertex with smallest distance from the heap, check if it has already been removed from the heap before. If it has, then remove this one too and continue. Otherwise, mark it as removed and visit all the neighbors.

请明确在什么地方在堆中的每个元素。然后，您可以执行被称为操作减少键你已经位于该元件上。

Keep an explicit pointer to where in the heap each element is. Then you can perform the operation known as "decrease-key" on the element that you've already located.

这篇关于如何更新优先级队列的关键在O（log n）的时间，Dijkstra算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！