Re: a recurring favourite: shortest route :)




"Jean-Claude Arbaut" <jean-claude.arbaut@xxxxxxxxxxx> wrote in message
news:BEDA03DE.56D7%jean-claude.arbaut@xxxxxxxxxxxxxx
>
>
>
> Le 18/06/2005 16:53, dans 25b49$42b4355f$50397e1f$16166@xxxxxxxxxxxxxx,
> « [jongware] » <jongware@xxxxxxxxxxxxxxxxx> a écrit :
>
> > "Jean-Claude Arbaut" <jean-claude.arbaut@xxxxxxxxxxx> wrote in message
> > news:BEDA0108.56CE%jean-claude.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 one-way?
> >>>
> >>> One-way 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 A-D spaced apart equally. A to D would (for example) go
> > A-C-D, D to A would be (by definition!) D-B-A ...
> > I'm still trying to visualize the algo ...
> >
>
> No, it can't work like that with two-way edges: if A-C-D is possible then
> D-C-A is also possible, and when you compare with D-B-A, D-C-A is shorter,
> otherwise the first path would have been A-B-D. You still pick the
shortest,
> don't forget :-) And there is no reason (and no definition) to prefer
D-B-A
> on D-C-A.

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. Algorithm-wise, 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 break-down which looks like I can actually
implement. Thanxx, both of you!

[jongware]


.