GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
184 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 (14.8k points) 15 151 316 | 184 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

+9 votes
Best answer

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

 

answered by Veteran (56.9k points) 36 189 500
selected by
wonderful and clear explanation..thanks a lot ..:-)
@debashish deka  you are  next RAVI SHANKAR MISHRA ...wonderful explanation
hey just need to ask you  that if we use (unsorted) array instead of sorted array.Then Analysis of Dijkstra would be-

1. The while loop will run for O(V)  times untill its empty

2. For extraction the minimum it will take O(V) time rather that O(1) since we have to search the entire array

3. we can do the decrease key operation in O(1) time since no overhead for maintaing the array sorted. This decrease key operation will  run for O(E) times (for every adjacent v for the vertex u. Sum of all length of all the adjacents)

Hence total Time Complexity would be (V.V+E.1)

=>O(V^2)

If this analysis is right can we say that dijkstra algo for unsorted array take lesse time that sorted array

Related questions

0 votes
1 answer
1
asked in Algorithms by Akriti sood Veteran (14.8k points) 15 151 316 | 163 views
+3 votes
2 answers
3
asked in Algorithms by Akriti sood Veteran (14.8k points) 15 151 316 | 98 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8264 Points

  4. srestha

    6296 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Notable Question KISHALAY DAS
Notable Question sh!va
Notable Question abhijeetbzu
Great Question jothee
Popular Question rahul sharma 5
Nice Question mohit kumar 5
Notable Question rishu_darkshadow
Nice Comment Pranay Datta 1
Copy Editor Shivansh Gupta
Nice Comment KULDEEP SINGH 2
27,324 questions
35,176 answers
84,108 comments
33,279 users