Implementation Challenges

 

1. Airline flight schedules define a natural graph, where the vertices are the airports and there is an edge between any two airports with direct flights between them whose weight is proportional to the distance between them. An extensive airplane data set due to Roberto Tammasia is available from the Algorithm Repository WWW/CD-ROM. Write a program that explicitly constructs the airport graph from this data set.

2. This problem is a follow-up to the exercise above. Changing planes repeatedly on connecting flights can be a hassle. Develop and implement an algorithm that finds the fewest flights needed to get from airport A to B, regardless of waiting time.

3. (*) This problem is a follow-up to the exercise above. Develop and implement an algorithm that finds the flight plan from airport A to B that minimizes the total distance traveled.
4. (*) This problem is a follow-up to the exercise above. Suppose that we must arrive at airport B at time T for an important scheduled meeting. Develop and implement an algorithm that finds the latest time one can leave airport A in time to make the meeting.
5. (*) This problem is a follow-up to the exercise above. In order to take advantage of a frequent flyer program, we might want to fly only on a particular airline. How can we modify the above solutions so as to accommodate such queries?
6. (**) This problem is a follow-up to the exercise above. A really devout frequent flyer might want to find the longest flight plan between airports A and B, so as to maximize the number of miles they get credit for. Develop and implement an algorithm to find the longest such route.