Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002: [Freeciv-Dev] Re: Priority queue for Dijkstra

# [Freeciv-Dev] Re: Priority queue for Dijkstra

[Top] [All Lists]

 To: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra From: Jason Short Date: Sat, 16 Mar 2002 13:01:11 -0500 Reply-to: jdorje@xxxxxxxxxxxx

```Gregory Berkolaiko wrote:
```
```Hi Jason,

On Sat, 16 Mar 2002, Jason Short wrote:
```
```Gregory Berkolaiko wrote:
```
```
```
quicksort is fast - O(n log n) in the average case, with a *small* constant factor (compared to other n log n sorts); the drawback is that it can be O(n^2) in the worst case (when everything is in the exact wrong position). What the "wrong position" is depends on the implementation of the quicksort; the standard qsort() function probably avoids the most likely cases.
```
```
```
```
Mmm, the one on my computer seems to be broken. I sort an array, than apply compare function to few neighbours and it changes sign!
```Or maybe my head is broken...
```
```
```
I've gotten this behavior when I make a mistake in writing the comparison function. If this function returns inconsistent comparisons the resulting sort is garbage.
```
```
But, any kind of sort is definitely inferior to a priority queue. A well-designed queue has a O(log n) insert time, and a small constant factor. There is little overhead and it is ammortized well. By contrast, implementing Dijkstra's correctly requires that the list *always* be sorted, because each element you pop off must be the smallest one. So to ensure correctness you'd really need to sort the list *every time you popped an item*.
```
```
```
that's right.
it wasn't very right of me to call it "from time to time".
the easiest alternative is to run find_minimal function, which is O(n).
```
```
Ouch.  Compared to O(log n), O(n) is awful.

And such will make the full search O(n^2) instead of O(n log n).

```
```The list of priorities for planes can be bounded by map.xsize + map.ysize
but with some potential problems.  If SINGLE_MOVE ever goes up from 3
thought, the maximum priority for land move will increase too, so heap
might be a good idea.

```
A heap is a good idea in any case - especially since such a structure has already been implemented, has it not? Can't you just use the existing priotiry queue class?
```
```
```
where is _the_ existing priority queue class?
```
```  get_from_mapqueue
```
routines? They are just priority-indexed arrays of LILO queues (with a weird implementation). This is a solid O(1) solution, unless you have too many indices.
```
```
Ahh, I see. So you're saying this "priority queue" will degrade badly as the number of possible priorities increases. (If you have a limited number of keys, you don't need to worry about quicksort. You can just do a bucket sort, which is O(n), and corresponds with what you describe for add_to_mapqueue/get_from_mapqueue.)
```
```
The solution is to either convert add_to_mapqueue/get_from_mapqueue to be a "real" priority queue, or write a new priority queue, or (best choice) find some library implementation of a priority queue.
```
```
As a side note, I though planes ignored SINGLE_MOVE and just took 1 unit of movement per tile?
```
```
```
In the SINGLE_MOVE sentence I was talking about land move.
```
The idea is that if you make railroads cost 1/10, the number of possible movecosts will be multiplied by 10 !
```
```
Yes, I see. And you're saying this is a problem given the current implementation of the priority queue.
```
jason

```