Consider n airports, labelled 1 through n. Each airport maintains a number of direct flights to other airports, represented by an edge with an associated cost. Since travel is currently restricted, one may only book direct flights—no airports will perform any transfers. However, things are beginning to open up again and airports are being slowly cleared to process transfers. These are done in order of label, so the first airport to allow transfers is 1, followed by 2, and so on. Once an airport is allowed to take transfers, flights through that airport may be booked. For example, consider the scenario depicted in Figure 1. When all airports are closed to transfers, flights may only be booked between airports connected by an edge. Thus, a flight from airport 5 to airport 2 may not be booked. However, once airport 1 is allowed to perform transfers, a flight from airport 5 to airport 2 may be booked via airport 1 with cost 9. Once airport 4 is allowed to perform transfers, a cheaper option is available: a flight from airport 5 to airport 2 via airport 4 has cost 3. Given a list of n airports, labelled 1, . . . , n in the order that they are cleared to accept transfers, and costs for direct flights between airports, define and prove a recurrence for the minimum cost of a flight from airport i to airport j if k is the latest airport that is allowed to process transfers.
Consider n airports, labelled 1 through n. Each airport maintains a number of direct flights to other airports, represented by an edge with an associated cost. Since travel is currently restricted, one may only book direct flights—no airports will perform any transfers.
However, things are beginning to open up again and airports are being slowly cleared to process transfers. These are done in order of label, so the first airport to allow transfers is 1, followed by 2, and so on. Once an airport is allowed to take transfers, flights through that airport may be booked.
For example, consider the scenario depicted in Figure 1. When all airports are closed to transfers, flights may only be booked between airports connected by an edge. Thus, a flight from airport 5 to airport 2 may not be booked. However, once airport 1 is allowed to perform transfers, a flight from airport 5 to airport 2 may be booked via airport 1 with cost 9. Once airport 4 is allowed to perform transfers, a cheaper option is available: a flight from airport 5 to airport 2 via airport 4 has cost 3.
Given a list of n airports, labelled 1, . . . , n in the order that they are cleared to accept transfers, and costs for direct flights between airports, define and prove a recurrence for the minimum cost of a flight from airport i to airport j if k is the latest airport that is allowed to process transfers.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
