IN JAVA:

Suppose you are given a timetable, which consists of the following:

A set A of n airports, and for each airport a A, a minimum connecting time c(a). You can ignore connection time for now.

A set F of m flights, and the following, for each flight f F:

Origin airport a1(f) A

Destination airport a2(f) A

Departure time t1(f)

Arrival time t2(f).

Describe an efficient algorithm for the flight scheduling problem.

1. Create a java implementation FlightScheduler.java that takes a txt file as commandline argument. The txt file contains the flight information as following , , , . For ex

SJC, NYC, 1200, 1430

NYC, IAD, 1530, 1700

SJC, IAD, 1230, 1800

Note that the times are given in military/aviation format so it's easier to compute. Build the graph based in this file.

2. Prompt the user for an origin, destination and a start time t. Implement an algorithm that will leave the origin after time t and get them to their destination in the shortest possible time. In the example above if origin == SJC, dest = IAD and start time is 1100, then SJC -> NYC -> IAD is a the shortest time.

3. Writeup only: What is the running time of your algorithm? Explain. Is your implementation a DAG, explain why/why not.

4. Extra Credit (20 points): Assume that each airport has a constant connection time of say 30 mins. Implement your algorithm to account for this.

5. Extra Extra Credit (20 points): Take an optional txt file as the second commandline argument. This lists the airports and the minimum connection times. Incorporate this into your computation. For example, if NYC as a minimum connection time of 90 mins then the passenger cannot make the SJC -> NYC -> IAD connection.