On Sat, 16 Jul 2005, George Sakkis wrote:
> "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
>> Dang! I was just about to point that out.
>> 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.
> - 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
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!
I do not think we will have to wait for very long.