1
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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.. $\endgroup$
    – munch
    Mar 10, 2010 at 1:53
  • $\begingroup$ 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)$. $\endgroup$ Mar 10, 2010 at 2:07

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