Suppose you are given a timetable, which consists of:
- a set of N airports, and for each airport
, a minimum connect time c(a)
- A set of M flights, and the following information,
for each flight :
- Origin airport
- Destination airport
- Departure time t1(f)
- Arrival time t2(f)
Give an efficient algorithm for the following problem:
Given airports a and b, and a time t, find a sequence of flights
that allows one to arrive at the earliest possible time in b when
departing from a at or after time t. Minimum connecting time
at intermediate airports should be observed.