GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
119 views
What is the time complexity to implement Dijkstra’s algorithm using a sorted array instead of heap for a Priority Queue?

for sorted array

let V be the number of nodes and E be the number of edges

1)extract min operation ---it will take constant time and it is repeated for V nodes.hence takes O(v) time.

2)decrease key operation occurs E times------now we can directly go and decrease the value of the node but we might have to sort the array again because after decreasing the key,array might not be sorted..so it will take VlogV time if we use merge sort.so ,total time is E*VLOGV

 

please verify this.
asked in Algorithms by Veteran (12.6k points)   | 119 views
it will be $O(v^3)$..
how..?can you tell whats wrong in my explanantion

http://stackoverflow.com/questions/2680365/running-time-for-dijkstras-algorithm-on-a-priority-queue-implemented-by-sorted

in this post,i saw it is also written that it is O(v^3) but tell me one thing,,after decreasing a particular key,dun w need to sort the array again cuz it might get unsorted..?

@Akriti

A small nitpick - You needn't to sort the whole array, just apply binary search and place the key there and shift the elements to a new position -> O(E.V) -> Now, the graph can either be sparse or complete.
ooh alright..thanks kapil..
exactly kapil ... that's what I was doing ... now uploaded !

1 Answer

+7 votes
Best answer

................

 

answered by Veteran (43.9k points)  
selected by
wonderful and clear explanation..thanks a lot ..:-)
@debashish deka  you are  next RAVI SHANKAR MISHRA ...wonderful explanation


Top Users Mar 2017
  1. rude

    5246 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2732 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1440 Points

  8. Bikram

    1432 Points

  9. Akriti sood

    1420 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,553 questions
26,901 answers
61,258 comments
23,269 users