Re: Python Programming Contest

On Sat, 16 Jul 2005, George Sakkis wrote:

"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).

Actually, it only computes shortest paths from the source to every node which is closer than the destination. Unless you keep computing after you've found your route!

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.

Ah, but in my approach, those rules are encoded in the structure of the graph; i don't think they leave you with a graph with any obvious exploitable properties.

To expand on that, rather than making a graph in which vertices are cities and edges are services, which then leaves me with the headache of finding a route in the face of shifting availability and weight of edges, i make each vertex a spacetime, rather than a purely spatial, location - 'Frankfurt on friday', for example, would be a different vertex to 'Frankfurt on monday'. Flights are then simply edges which link the origin city on the day they depart to the destination city on the next day; their weight is the cost of the flight. City X on day N is always linked to City X on day N+1 by an edge representing the option of staying in a hostel. Vertices corresponding to the destination city on any day are all linked to a special goal vertex by length-0 edges, so if you can make it to the destination at any time, you win. You could put nonzero weights on those edges if you liked, to capture your preferences about when you wanted to arrive (if you were willing to pay 15 pounds more to get there on tuesday, you'd set the weight of links from tuesday to the goal to -15, for example). You'd probably also want a special start node linked to your home airport on every day by length-0 edges.

I can't see any properties of the resulting graph that are particularly interesting. The fact that flight prices are not correlated with physical distance makes an A*-like approach impossible.

Actually, there is one thing - the number of edges you need to traverse to get from any vertex to any other (apart from the start and goal vertices) is always the same, regardless of the route taken, since each edge corresponds to one day's actions, and any given pair of vertices are a certain number of days apart. Ah, is that what you were hinting at? I'm still not sure how you could use this, though!

tom

--
I do not think we will have to wait for very long.
.

Relevant Pages

  • Re: Graphs and reducibility(or something like that)
    ... results in graph theory ... Wis the "weight" of the edge NiNj which, for this problem, is ... This is kirchoffs current law which just says that the sum of the ... weights that are differential equations and inside those equations I have ...
    (sci.math)
  • Re: Bus/train timetable search algorithm
    ... The simplest way would be a directed graph with one edge per unique combination of places A and B where B immediately follows A in a timetable. ... you can use Dijkstra's algorithm on the graph to find the quickest "theoretical" route from starting point to destination. ... From the above you can create a new, smaller graph comprising all the nodes/edges that were visited/traversed in the quickest routes, which should be amenable to an exhaustive search - taking into account start time, timetables, minimum connection times, and anything else you want. ... flight flight B if B departs from A's destination, ...
    (comp.programming)
  • Re: Question about heavier students...
    ... feature of the graph and not a limitation. ... it says nothing about a limit for the combined front-seat weight. ... capacity for baggage areas 1 and 2 is 120 lbs". ...
    (rec.aviation.student)
  • Re: create a running subtotal in a query and then graph results
    ... I am trying to create a running subtotal in a query and then graph the ... the entire record set, not by city, so that did not work. ... using incorrect criteria. ...
    (comp.databases.ms-access)
  • Re: Question about heavier students...
    ... feature of the graph and not a limitation. ... it says nothing about a limit for the combined front-seat weight. ... capacity for baggage areas 1 and 2 is 120 lbs". ...
    (rec.aviation.student)