8
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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