Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Title says it all. Why is the choice of data structure for Dijkstra's algorithm a priority queue, rather than a simple sorted list?

share|improve this question

closed as off topic by David Eppstein, Harry Gindi, Noah Snyder, Reid Barton, S. Carnahan Mar 10 '10 at 2:44

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
This is about undergraduate level algorithms rather than research level mathematics. And it reads like a homework question. –  David Eppstein Mar 10 '10 at 2:02
    
You're right about undergraduate level algorithms, but it's not homework. –  munch Mar 10 '10 at 2:07
1  
Did you try StackOverflow? –  Harry Gindi Mar 10 '10 at 2:15
    
@fpqc it's not really programming. i'd call this math.. –  munch Mar 10 '10 at 2:17

2 Answers 2

Consider the running time for adding a new element to a sorted list, keeping the list sorted. If the list is an array, you can find the insertion point in $O(\log n)$ steps, where $n$ is the current size of the list. But then you have to make room for the new element by shifting all the elements behind it one step back, and that takes $n/2$ steps on the average. Or you could use a linked list, but then binary search is not available, and it takes $n/2$ steps (on the average) to find the insertion point (and $O(1)$ to do the actual insertion). For a properly implemented priority queue, insertion is $O(\log n)$, and so is fixing up the queue after removing the smallest member.

share|improve this answer

See http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Running_time.

share|improve this answer
    
I read that, but it doesn't seem totally legit. In the end, it's performing heap sort on the edges, which is O(nlogn). Sorting a list and extracting the min element is O(nlogn). Seems to be equivalent runtimes.. –  munch Mar 10 '10 at 1:53
    
But in Dijkstra's algorithm, you don't just want the minimum member once. Instead, you have a collection of edges, and repeatedly remove one (the minimum) and add more, looking for the minimum all over again, and so forth. Estimating the running time of all these operations seems a bit more involved than just waving your arms and saying $O(n\log n)$. –  Harald Hanche-Olsen Mar 10 '10 at 2:07

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