Complete.Org: Mailing Lists: Archives: freeciv-dev: August 2002:
[Freeciv-Dev] Warmap

[Freeciv-Dev] Warmap

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Warmap
From: Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx>
Date: Mon, 12 Aug 2002 22:30:48 +0100 (WET DST)

Regarding warmap speedups:

If anyone feels up to implementing them, there are some algorithms which
promise to solve the single-source problem:

in linear time for undirected planar graphs:

IIRC Dijkstra takes quadratic time in our implementation.

=== References:

Faster shortest-path algorithms for planar graphs:

Undirected single source shortest paths with positive integer weights in
linear time:

On RAM priority queues:

Andrew Goldberg's network optimization library:

Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa

[Prev in Thread] Current Thread [Next in Thread]