# Pathfinding when the graph varies over time

Let's say I want to simulate a very large number of travelers booking flights. For example, a traveler might want to fly from New York to New Delhi. There's no direct flight from New York to New Delhi, but there's a flight from New York to London, and from London to New Delhi, so our traveler books those two flights. Each traveler is looking for the route with the lowest cost (where cost is some function of travel time, total fares, and various other factors; this function may vary depending on the traveler). A simple pathfinding problem so far.

But the actual problem is a little messier than that. There might be a flight from London to New Delhi on Friday, but not on Saturday. So it won't do any good to arrive in London after the last plane for New Delhi for the week has already left. It's as if the graph changes with every step, because time passes with each step and the available flights change with time. (However, we're planning out the whole trip in advance; no time is actually passing during the pathfinding process.)

I can think of ways to compensate for this. For example, I could use A* with a graph where, rather than each node being a city, it could be a city and a time, so that London on Friday and London on Saturday are considered separate nodes. However, I'm not sure this is the best way. Since I'm simulating a very large number of travelers, I need this algorithm to be as fast as it can possibly be, so long as memory usage is reasonable. What literature exists on this subject?

• Each traveler is looking for the route with the lowest cost, where cost is some function of travel time, total fares, and various other factors; this function may vary depending on the traveler. I've edited the question accordingly. But if there are other algorithms that assume that the cost function doesn't change depending on the traveler, I'd be interested in those as well; I could probably work with such a system. – Kef Schecter Mar 4 '17 at 7:54