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]


.



Relevant Pages

  • Re: [cryptoapi/sysfs] display cipher details in sysfs
    ... > the attached code (does compile, don't think that it will boot, just ... > algorithm the preference is looked after (it should be made a writeable ... > algorithm very intuitive). ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: Seeing VERSIONINFO under Vista?
    ... I'd guess the algorithm is not smart enough to know what it is ellipsing so you just get the first part of the text and the last part. ... useless IDD_ in preference to something that actually mattered! ...
    (microsoft.public.vc.mfc)