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

# [Freeciv-Dev] Priority queue for Dijkstra

[Top] [All Lists]

 To: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Priority queue for Dijkstra From: Gregory Berkolaiko Date: Sat, 16 Mar 2002 16:46:31 +0000 (GMT)

```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.

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).

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?

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.

Best wishes,
G.

P.S. Oh ye, computer scientists, please spare me from the wrath of you
flamethrowers if I erred in the above message.

```