Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap):

For each vertex y such that it is a node for it in a heap and there is an edge (x,y) in a graph:

1) Dist[y] = min(Dist[y], Dist[x] + w(x,y))

2) Update y's node in the heap

It is also said that the complexity of these steps for the whole algorithm is O(ElogV).

But I can't undestand why the step "that it is a node for it in a heap" doesn't influence on complexity in the bad way. Because it means that we should find every neighbor of x in the heap, but there are no efficient ways of searching for node in the heap (only linear search comes to my mind), and it means that for each y we should:

1) Find it in the heap - which takes O(number of nodes in the heap) watches

2) Update it - which takes O(logV) time

This way, it will take O(V*E*logV+(V-1)*E*logV+...) = O($V^2$*E*logV), since the number of nodes in the heap decreases on each step by 1. Am I losing something?

share|cite|improve this question
up vote 3 down vote accepted

One can store an array of pointers, one for each node, that points to the location of that vertex in the heap used in Dijkstra's algorithm. When each heap operation is applied (e.g. the removal of the top element), one can easily update this array for each swap operation in memory that is thus made. (So one can define a modified heap data structure such that each element in the heap has a key (i.e. a pointer), and one can immediately find the element in the heap for a given key, even if the heap changes.) This way, if you want to look up a node in the heap, you don't need to do a linear search, but just check the pointer for that node.

share|cite|improve this answer

Actually, we don't need to search for a node in a heap directly. We can imply a node is there if it were visited, but not yet extracted from the heap. So, by maintaining the two sets of vertices (visited and extracted), we can achieve this.

Furthermore, we can avoid changing distances in a heap altogether. Just always push a node with a new distance to the heap, ignoring possibility of it being already there. This approach makes the heap at most |E| elements in size (note that it will not affect the complexity, as O(logV) = O(logV^2) = O(logE)). Upon extracting a node from the heap, check whether it belongs to the "extracted" set. If it does - simply discard it. Employing this approach, we don't even need the visited set - we will push a node to the heap if it wasn't yet extracted. We will stop the algorithm when the heap is empty.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.