[Freeciv-Dev] Re: Path finding: dijkstra vs a*

[Trent Piepho <xyzzy@xxxxxxxxxxxxx>]

On Tue, 4 Sep 2001, Justin Moore wrote:
> > Has anybody considered implementing A* instead of the Dijkstra
> > algorithm (which is AFAIK currently used)? Since I'm unfamiliar with
> > A* can this result in a performance gain? AFAIK the method
> > really_generate_warmap has top spot on the profile.
> 
>    From what I know of the really_generate_warmap function, A* won't be a
> big help.  A* is a gain if you're actually searching for something
> (AFAIK).  It looks like the function *has* to visit all the nodes since it
> needs a value for each.  I know there are better ways to do the warmap
> (dynamic programming methods come to mind) but I forget the best way to
> implement them.

An A* search and Dijkstra's algorithm do different things.  Dijkstra is for
finding the shortest paths from a node in a graph to all other nodes.  An A*
search is one type of method for seaching a graph for the shortest (or any)
path from one node to another node.  An A* search uses a heuristic to evaluate
the estimated cost of the remaining path.  The node in the seach tree with the
lowest cost - length of path taken plus estimated path remaining - is
evaluated first. 

If the heuristic for estimating the remaining path was always zero, then the
A* search would be in effect a breadth-first search.  If the heuristic is
always less than or equal to the true remaining cost, then the A* search will
find the shortest path.  If the heuristic is not always less than the true
cost, then the true shortest path may not be found.

Freeciv used to use an A* search to make things faster.  This search would
sometimes not find the shortest path.  It turns about that because railroads
use zero movement, a heuristic that will find the shortest path (always
returns <= the true remaining cost) is so conservative that it is little
better than an simple breadth-first (heuristic h(x) = 0) search.  And if
you're going to do a breadth-first search, you might as well use Dijkstra's
algorithm to get the entire shortest path graph, which is the same cost.