[Freeciv-Dev] Re: find_the_shortest_path()

[Raahul Kumar <raahul_da_man@xxxxxxxxx>]

--- Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
> 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 seems to be a simple solution to this problem.
Introduce a cost for railroad movement !!!! 
> > 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
> 



__________________________________________________
Terrorist Attacks on U.S. - How can you help?
Donate cash, emergency relief information
http://dailynews.yahoo.com/fc/US/Emergency_Information/