5

I have the following scenario:

I want to find a flight between two cities: A and B. There is no direct flight from A to B; so, I need to find a connecting flight with the lowest cost.

In addition, the air ticket is not fixed. It depends on the time that I buy it; for example, the price will be cheaper if I buy it early.

Moreover, the time affects the flight too; for example, there is only one flight from C to D on May 31 at 7 AM. If the plane flies from A to C on May 31 at 8 AM, I miss the flight. For this reason, I represent the cities as vertices of a graph. The path AB exists if there is a valid flight from A to B. The weight will be the ticket fee.

Is there any idea or suggestion for my problem?

Thanks

fjarri
  • 9,546
  • 39
  • 49
Thinh Phan
  • 655
  • 1
  • 14
  • 27
  • Sounds like a reasonably simple [A*](http://en.wikipedia.org/wiki/A*) problem (you'll obviously also have to keep arrive dates at each city), but rather than only keeping the best path to a given city, you'll have to keep all the paths (though you can remove those that both arrive later and are more expensive than another path). – Bernhard Barker May 31 '13 at 14:35
  • [Related question](http://stackoverflow.com/questions/15938954/is-there-is-a-route-from-city-a-to-city-b-in-no-more-than-x-days), though it minimizes days rather than cost. – Bernhard Barker May 31 '13 at 14:40

2 Answers2

4

I answered once a very similar question I am pretty sure same idea can be used here. The idea is to use a routing algorithm, designed for internet routers - which are dynamic and constantly changing. The algorithm designed for it is Distance Vector Routing Protocol.

The suggested implementation is basically a distributed version of Bellman-Ford algorithm, that modifies itself once there is a change on the weights of each edge in order to get the new optimal path.

Note that the algorithm has draw backs, mainly the count to infinity problem.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
1

The usual way to deal with not being in the right place at the right time is to make the nodes represent a specific place at a specific time. Then a flight from C to D that departs on May 30 at 9PM and arrives May 31 at 7AM corresponds to an arc from node C_May30_9PM to D_May31_7AM. You also need arcs that correspond to waiting around, e.g., D_May31_7AM to D_May31_8AM.

I'm not sure there's much to say about purchasing tickets at the level of detail you've described.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120