how to Update a key in Priority Queue in O(log n ) time in dijkstra's algorithm?

Question

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)

What My thought process is:

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.

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

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

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

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 )

Answer 1

Regarding the basic approaches mentioned by @Ivan Vergiliev here, I had a long discussion about this back in 2002 (first post). The difference is in the space complexity: if you just do naïve option 1, you get space complexity O(E), which is equal to O(V²) worst-case, rather than O(V) for option 2.

I came up with an optimization that helps reduce queue growth for option 1 (includes proof of correctness and of time complexity from someone else in a follow-up message in that thread). But it still requires O(|E|) space worst-case, in a heavily connected graph. If you trace through it with a graph where the start vertex fans out to N vertices, each of which is connected to all members of another group of N vertices, and all edge weights are 1, you'll end up with N² queue entries, which is O(|E|).

My variant is:

DIJKSTRA(G, s, w)
  for each vertex u in V
    d[u] := infinity        // stores each vertex's distance from s
    p[u] := u               // stores each vertex's predecessor on shortest path 
  end for

  S = Ø
  INSERT(Q, (s,s,0))
  while (Q != Ø)
    u,t,x := EXTRACT-MIN(Q)
    if u not in S
      d[u] = x // optional! d not needed for algorithm
      p[u] = t // also optional
      S := S U { u }
      for each vertex v in Adj[u]
        if v not in S // optimization - first path to v is always shortest
          INSERT(Q, (u, v, x + w(u,v))) // put the path in the queue
        end if
      end for
    end if
  end while

Where:

• G is the graph

• s is the start vertex

• w(u,v) is the weight (length) of the edge from u to v in G

• S is a set of vertices

• Q is a heap of triples (p, v, l) ordered by l

  • p is the predecessor of v on the shortest path to s
  • l is the shortest distance from s to v

• d is a map from vertex to distance

• p is a map from vertex to vertex

• On completion, for each vertex u,

  • d[u] holds the shortest distance from s to u
  • p[u] holds the predecessor of u on the shortest path from s to u

Answer 2

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

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.

2. 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.