[Freeciv-Dev] Re: find_the_shortest_path()

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Sep 18, 2001 at 04:37:11AM -0400, Jason Dorje Short wrote:
> > 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.
> 
> There is no single shortest path, correct.  There are infinitely many
> equally short shortest paths; the only reason to prefer one with fewer
> steps is elegance.
> 
> Dijkstra's algorithm does assure you will never go in a loop; this is a
> trustworthy property.  You are always guaranteed to find one position on
> the loop before you find the loop itself.  However, if there is more
> than one shortest path there is no guarantee that you will find the path
> with the fewest steps.
> 
> Introducing a second measurement of path cost would solve this, but I
> think "number of steps taken" is a much more valid measurement than
> "number of railroad steps taken".  The implementation probably already
> tends to do this simply because it uses a queue, so 

> I don't think it should be much of a problem.

Ack.

> > > 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.
> 
> Ugh.
> 
> Well, here's a start.

Looks ok. However I have to verify this. And there are other patch
already in the queue (your cleanup patch, remove dir_ok,
straightest_direction with scalar product, the trireme patch, the two
city report dialog patches and making a MAPSTEP patch if nobody turns
up) and in addition to this I hope to finally get a polished version
of the CMA out of the door. So please go further to clean up the goto
handling.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "> WHY?! Isn't it better to put $(shell cat cscope.files) on the list of
  I only have a yellow belt in makefile kungfu.  These fancy gnu make things
  are relatively new to some of us..."
    -- Mark Frazer to Vassilii Khachaturov in linux-kernel