Question

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

Answer 1

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.

Answer 2

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

Answer 3

You have to understand a priority queue is an abstract data structure. There isn't really "a priority queue", there's implementations of the idea of a priority queue.

You could very well keep a list, sort it, and then that would be your priority queue. The thing is, that will (likely) have a worse running time than other ways of implementing a priority queue. Keep in mind complexity deals with asymptotic running time. In practice, there are still constant in there and they make a difference, so we want to use a better implementation of a priority queue than constantly sorting an entire list.

So don't let "priority queue" versus "sorted list" confuse you; they are conceptually one in the same.