[Freeciv-Dev] Warmap

[Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx>]

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.

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