# Re: a recurring favourite: shortest route :)

*From*: "[jongware]" <jongware@xxxxxxxxxxxxxxxxx>*Date*: Sat, 18 Jun 2005 18:00:11 +0200

"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]

.

**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:*Jean-Claude Arbaut

**Re: a recurring favourite: shortest route :)***From:*[jongware]

**Re : a recurring favourite: shortest route :)***From:*Jean-Claude Arbaut

- 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):