[Freeciv-Dev] Re: find_the_shortest_path()

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Sep 18, 2001 at 03:38:15AM -0400, Jason Dorje Short wrote:
> Raimar Falke wrote:
> > 
> > On Tue, Sep 18, 2001 at 02:41:55AM -0400, Jason Dorje Short wrote:
> > > I have several comments/questions on find_the_shortest_path() in
> > > server/gotohand.c.
> > >
> > >
> > > A comment [1] says:
> > >
> > > /*
> > > To avoid RR loops (which may cause find_a_direction() to move a unit in
> > > cute little cycles forever and ever...), when we have more than one path
> > > to a tile and the second one is via RR (move_cost 0), we do NOT mark the
> > > extra path.
> > > */
> > >
> > > However, Dijkstra's algorithm doesn't have this problem since any time
> > > the point is encountered a second time and the movement cost is no less
> > > it is not considered a second time.
> > 
> > You may have two paths to a certain position. These two paths have the
> > same move costs. The first path has 3 rail-road steps and the second
> > has 6544 rail road steps. You find the second path before the first.
> 
> That may be possible (although I assume the implementation of the
> algorithm will prevent it by looking at the fewest-step path first; I
> have not checked), but it does not make the comment any more correct.
> 
> The comment claims that some checking for RR paths is done. 

> In fact no such checking is done, as the later comment attests -
> things just work out because Dijkstra's algorithm already takes care
> of this problem.

In a mathematical and formal way there is no shortest path if there
are edges in the graph which have no cost. IMHO a clean solution is to
create a compound cost which is (normal_move_cost,
rail_road_steps_taken). IMHO it wrong to trust this property of the
Dijkstra algorithm.

> As for the rest, I think a lot of cleanup could be done to this code -
> but it will be difficult to guarantee the correctness of the new code
> without a full understanding of the current code, which will take some
> time.  A simple replacement of parts of the code with function calls
> should be easy enough, though.

IMHO it can and should be rewritten from scratch. I see no problem of
replacing the current implementation if a certain amount of people can
assure that the replacement is correct in the mathematical way. But it
is your time you invest in this.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  One nuclear bomb can ruin your whole day.