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 12:06:50 -0500 Reply-to: jdorje@xxxxxxxxxxxx

```Gregory Berkolaiko wrote:
```
I am now hacking at the air route-finding functions, trying to adapt it to AI needs. As a blueprint of a "good" implementation I am using Raimar's goto_agent code which uses a list and a hash table to hold reachable tiles for Dijkstra algorithm.
```
Hmm, I have not seen this code.

```
The list is sorted from time to time to find the next nearest tile. This aroused my suspicions, since we really need a priority queue and the naive implementation of a priority queue is just a list with a find_maximum_element function --- an O(n) algorithm. Being a poorly educated peasant boy, I didn't know how fast is qsort, but I went to the big town and found a nice set of lecture notes:
``` http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/index.html
where I am told that qsort is O(n log(n)), with a potentially large
constant factor (plus genlist stuff on top of that).
```
```
```
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.
```
```
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*.
```
```
```The current implementation of priority queue in gotohand.c is actually
O(1) --- as far as I can tell --- due to the limited set of possible
```
priorities. But it's a bit ugly. Maybe there is a standard heap method ( heap is O(log(n)) ) somewhere in C or hidden in freeciv code?
```
```
No doubt there is some kind of heap or other binary-tree-type structure down there somewhere. If not, I'm pretty sure somebody needs to be published :-).
```
```
```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?
```
```
As a side note, I though planes ignored SINGLE_MOVE and just took 1 unit of movement per tile?
```
jason

```