Re: a recurring favourite: shortest route :)
 From: "[jongware]" <jongware@xxxxxxxxxxxxxxxxx>
 Date: Sat, 18 Jun 2005 18:00:11 +0200
"JeanClaude Arbaut" <jeanclaude.arbaut@xxxxxxxxxxx> wrote in message
news:BEDA03DE.56D7%jeanclaude.arbaut@xxxxxxxxxxxxxx
>
>
>
> Le 18/06/2005 16:53, dans 25b49$42b4355f$50397e1f$16166@xxxxxxxxxxxxxx,
> « [jongware] » <jongware@xxxxxxxxxxxxxxxxx> a écrit :
>
> > "JeanClaude Arbaut" <jeanclaude.arbaut@xxxxxxxxxxx> wrote in message
> > news:BEDA0108.56CE%jeanclaude.arbaut@xxxxxxxxxxxxxx
> >>
> >> Le 18/06/2005 16:30, dans 95e88$42b42ff9$50397e1f$14647@xxxxxxxxxxxxxx,
> >> « [jongware] » <jongware@xxxxxxxxxxxxxxxxx> a écrit :
> >>
> >>> "Frank Lin" <spamfree@xxxxxxxxxx> wrote in message
> >>> news:iuVse.19933$Le2.127651@xxxxxxxxxxxxxxxxxxxxxxx
> >>>> Is the trip a loop or oneway?
> >>>
> >>> Oneway only. Though I fail to see why this would change the
algorithm,
> >>> e.g., shortest path from A > B *equals* shortest from B > A, so a
> > round
> >>> trip would *also* be the shortest loop ... innit?
> >>> The naive algorithm does not guarantee A > B equals B > A, where
> > common
> >>> sense sez it should.
> >>
> >> But the naive algo is wrong anyway... I think the question was "loop
> > without
> >> passing by the same path". Maybe Frank had the hamiltonian path in
mind.
> >
> > ahhh I made another bad assumption ... shortest path from A > B does
not
> > *have to* equal B > A.
> > Imagine 4 points AD spaced apart equally. A to D would (for example) go
> > ACD, D to A would be (by definition!) DBA ...
> > I'm still trying to visualize the algo ...
> >
>
> No, it can't work like that with twoway edges: if ACD is possible then
> DCA is also possible, and when you compare with DBA, DCA is shorter,
> otherwise the first path would have been ABD. You still pick the
shortest,
> don't forget :) And there is no reason (and no definition) to prefer
DBA
> on DCA.
Yup, got that. There is no preference for the *first* jump to be long or
short. My (constructed!) example is sth like A (2)> B (2)> C (2) > D,
with a max single jump range of 5. So from A to D the *longest* possible
first jump would be A > C, then C > D, but the other path (A > B, then
B > D) would yield exactly the same result. As there is no preference,
there are 2 valid solutions. Algorithmwise, it does not matter which one is
presented as solution; so a nice feature would be to show all possible
paths, and the user could decide for himself which one to take. In the other
thread Willem gives a full breakdown which looks like I can actually
implement. Thanxx, both of you!
[jongware]
.
 References:
 a recurring favourite: shortest route :)
 From: [jongware]
 Re: a recurring favourite: shortest route :)
 From: Frank Lin
 Re: a recurring favourite: shortest route :)
 From: [jongware]
 Re : a recurring favourite: shortest route :)
 From: JeanClaude Arbaut
 Re: a recurring favourite: shortest route :)
 From: [jongware]
 Re : a recurring favourite: shortest route :)
 From: JeanClaude Arbaut
 a recurring favourite: shortest route :)
 Prev by Date: Re: a recurring favourite: shortest route :)
 Next by Date: Re: a recurring favourite: shortest route :)
 Previous by thread: Re : a recurring favourite: shortest route :)
 Next by thread: Re : a recurring favourite: shortest route :)
 Index(es):
Relevant Pages
