Title says it all. Why is the choice of data structure for Dijkstra's algorithm a priority queue, rather than a simple sorted list?
4
-
2$\begingroup$ This is about undergraduate level algorithms rather than research level mathematics. And it reads like a homework question. $\endgroup$– David EppsteinCommented Mar 10, 2010 at 2:02
-
$\begingroup$ You're right about undergraduate level algorithms, but it's not homework. $\endgroup$– munchCommented Mar 10, 2010 at 2:07
-
1$\begingroup$ Did you try StackOverflow? $\endgroup$– Harry GindiCommented Mar 10, 2010 at 2:15
-
$\begingroup$ @fpqc it's not really programming. i'd call this math.. $\endgroup$– munchCommented Mar 10, 2010 at 2:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Mar 10, 2010 at 2:15
$\begingroup$
$\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$– munchCommented 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$ Commented Mar 10, 2010 at 2:07