Title says it all. Why is the choice of data structure for Dijkstra's algorithm a priority queue, rather than a simple sorted list?
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.
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.