"Tom Anderson" <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
