Find the shortest path in a graph with dynamic weight

Question

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

Answer 1

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.