[Freeciv-Dev] Re: Warmap

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Mon, 12 Aug 2002, Vasco Alexandre Da Silva Costa wrote:

> Regarding warmap speedups:
> 
> If anyone feels up to implementing them, there are some algorithms which
> promise to solve the single-source problem:
> <http://www.boost.org/libs/graph/doc/graph_theory_review.html>
> 
> in linear time for undirected planar graphs:
> <http://mathworld.wolfram.com/PlanarGraph.html.html>.
> 
> IIRC Dijkstra takes quadratic time in our implementation.

Yes I did some research on it previously, in particular read the papers by
Thorup and Goldberg that you are referring to below.  Some of the
algorithms you mention are not applicable to our case which is non-planar
graph with non-negative (rather than strictly positive) weights.

Besides AFAIU the current implementation _is_ linear, at least in the 
sense that Thorup's algorithm is linear (his discovery was that you can 
pile nodes into a bucket list even though your weights are not integers -- 
this is already done in the current warmap).  My own empirical discovery 
was that if in our case you go for priority queue (log(n) time) rather 
than for bucket list (constant time) you get a speed-up: the bucket list 
is too expensive to set up for the small $n$ we usually get.

G.

 > 
> === References:
> 
> Faster shortest-path algorithms for planar graphs:
>   <http://citeseer.nj.nec.com/henzinger94faster.html>
> 
> Undirected single source shortest paths with positive integer weights in
> linear time:
>   <http://citeseer.nj.nec.com/thorup99undirected.html>
> 
> On RAM priority queues:
>   <http://citeseer.nj.nec.com/thorup96ram.html>
> 
> 
> Andrew Goldberg's network optimization library:
> <http://www.avglab.com/andrew/soft.html>
> 
> ---
> Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa
> 
> 
>