Re: Python Programming Contest

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.

I don't foresee anyone getting a more efficient solution than what they can find in hundreds of algorithms textbooks. If this is indeed the case it should just come down to whoever can pull the narliest tricks to create a fast python implementation of the algorithm.

I guess part of the challenge is seeing through the description to the underlying problem - in this case, seeing that this can be cast as shortest-path. Not everyone would necessarily realise that! In particular, the fact that the available flights, and their prices, can be different on different days could well throw people.

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. For instance, if your graph is a road network, you can put a lower bound on the distance from any vertex to the goal (being the straight-line distance between them - no path over actual roads can be any shorter than that), which allows you to do an A* search, which is a lot faster than Dijkstra. My own journey planner is also a case of this - i exploit various obvious properties of tube trains to avoid examining a large number of possible but daft travel plans.

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

tom

--
taxidermy, high tide marks, sabotage, markets, folklore, subverting, .
.

Relevant Pages

  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: combinatorial optimization problem (six-pick wager grouping)
    ... versed in graph theoretic approaches could comment on my ideas below - ... I'n not a graph theorist, nor a graph algorithm buff, so I can't really ... attempt to merge it with each bet already in the pool. ... million edges when I ignored wager size. ...
    (comp.programming)
  • Re: Pathfinding in community
    ... > Each member is able to add his own contacts at the community. ... Dijkstra's algorithm is simply a refined breadth first search. ... In your case all the edges on the graph have the same weight, ... I would suggest loading this data into an array of arrays. ...
    (comp.lang.php)