[Freeciv-Dev] Priority queue for Dijkstra

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.