[Freeciv-Dev] Re: Priority queue for Dijkstra

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Mar 16, 2002 at 04:46:31PM +0000, 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.

> The list is sorted from time to time to find the next nearest tile.  

Before every get.

> 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?

None that I know of. I found these (GPLed):
    223     864    5646 heap.c
     77     356    2206 heap.h

Do you think that a "real" priority queue performance or does it will
"only" increase readability?

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  A supercomputer is a computer running an endless loop in just a second