Dijkstra algorithm complexity anaylsis misunderstanding

Question

Given the following algorithm from Cormen book:

DIJKSTRA(G,w,s)

1. INITIALIZE-SINGLE-SOURCE(G,s)
2. S <-- {0}
3. Q <-- V[G]
4. while (Q != {0})
5.    do u <-- extract-min(Q)
6.    s <-- s U {u}
7.    for each vertex v at Adj(u) 
8.            do RELAX(u,v,w)



RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)
       pie(v) <--- u

Our prof told us that if we use Binary Heap, the Relax operation takes O(log|V|), and therefore the loop at line 7-8 takes O(|E|*log|V|).. (If we use linear queue then the relax takes O(1)). Ive been searching google for a while and just cant find a good explanation for that. why does the relax operation take O(log|V|) when we use binary heap? Would love to get some help. thanks.

There seems to be something missing. The only place where you insert something into Q is line 3, and there you insert only one node of the graph? What's pie? — Sebastian
– Sebastian, Commented Apr 12, 2013 at 19:11

siddstuff · Accepted Answer · 2013-04-12 19:22:59Z

1

In Relax funciton , key value at d[v] is updated , we need to maintain the min heap again because it may violate the property of mean heap , so entire procedure of Relax takes O(log v) time. min heap is maintained and it is ready to extract the next min value.

RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)        //* updation.
       pie(v) <--- u

answered Apr 12, 2013 at 19:22

siddstuff

1,2554 gold badges17 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

masotann · Accepted Answer · 2013-04-12 19:29:19Z

1

I believe once you relax a node, you will have to place them in the correct node in the binary heap. Worst case, if the current node has a horrible distance value and is a leaf node in your binary heap, and you just found a really good way to get to that node, you would have to move that node from the bottom of the heap towards the top to maintain the min heap property. The number of levels a node may need to move is log(V) -> O(log(V))

edited Apr 12, 2013 at 19:29

answered Apr 12, 2013 at 19:06

masotann

91110 silver badges30 bronze badges

Comments

DontVoteMeDown · Accepted Answer · 2013-11-21 13:06:27Z

1

In my opinion, RELAX takes O(1). Since every edge is looked at exactly once, this generates O(E). Point is that extract-min takes O(log(V)) and is used V times, which accounts for O(V log(V)).

So all in all, Djikstra runs in O(V log V + E)(see this page), independent of which heap structure is used (see this post).

Aside of that, running min-heap whenever calling RELAX operation (instead once every iteration of 4-8) would produce a huge time overhead.

edited Nov 21, 2013 at 13:06

DontVoteMeDown

21.5k10 gold badges72 silver badges113 bronze badges

answered Nov 21, 2013 at 12:48

Niklas F

111 bronze badge

Comments

Priya · Accepted Answer · 2014-09-10 14:12:34Z

1

If we are maintaining min heap then extract-min(Q) will take O(1) time. O(log V) is only due to updation and maintaining min heap.

answered Sep 10, 2014 at 14:12

Priya

112 bronze badges

Collectives™ on Stack Overflow

Dijkstra algorithm complexity anaylsis misunderstanding

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related