Python Programming Contest

[George Sakkis]

"Tom Anderson" <twic at urchin.earth.li> wrote:

> On Sat, 16 Jul 2005, Joseph Garvin wrote:
>
> > Someone correct me if I'm wrong -- but isn't this the Shortest Path problem?
>
> Dang! I was just about to point that out.
>
> [snipped]
>
> But yes, this is basically about who can write the fastest implementation
> of Dijkstra's algorithm. I've got one somewhere - i have a half-finished
> journey planner for the London Underground! - so maybe i should enter ...
>
> Hmm. Actually, Dijkstra's algorithm isn't always the fastest way to find
> the shortest path. The thing is, it's fully general, so it works on
> absolutely any graph; if the graph you're traversing has particular
> properties, you might be able to leverage those to find a solution faster.
> [snipped]

Yes, that's right. Moreover, Dijkstra's computes the shortest path from a given start to *all* nodes
in the network, which is usually an overkill if all you want is the shortest path to one (or a few)
node(s).

> I can't immediately see any properties of this network that could be
> exploited, but that doesn't mean there aren't any.


Hints:
- You have to take exactly one decision (flight or stop) every single day until you reach the
destination; no more, no less.
- There is no time machine; days pass in one direction only, one at a time.

George