Re: Python Programming Contest

"Tom Anderson" <twic@xxxxxxxxxxxxxxx> 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


.

Relevant Pages

  • Re: Representing a Tree in Python
    ... other nodes in the graph. ... Dijkstra code you are using it may be possible to help you with the ... finds shortest path between only two nodes. ... And what is the best way to represent a tree in Python?. ...
    (comp.lang.python)
  • Re: Graph optimization
    ... represented in the form of a graph. ... I have to add up all the weights to form the ... algorithm is going to be the best for finding the shortest path ...
    (comp.programming)
  • Re: Changing minimization to maximization, do the following problems change?
    ... if I know how to solve shortest path problem and then I ... you said this is NP-complete problem; ... Finding the longest path between two vertices in an acyclic graph ...
    (comp.theory)
  • Re: Reply: Time dependent shortest path
    ... For the single-pair problem (shortest path from A to B), take the graph ... A to B will include either the quickest path from A->C or the quickest ...
    (comp.theory)
  • Re: Longest path
    ... similar graph with all edges values negated. ... since the shortest path will go through this circle inifinte ... but finds out if there are negative-sum circles. ... circle, so that's gonna be a problem. ...
    (comp.theory)