I’m sure we are all familiar with trips that take a couple (or more) shorter flights with layovers
in between to get to our final destination. Sometimes this is done because of total price, total
time, or the fact that there is no direct flight from where we are to our destination. In this
project, you will use information on flights including the duration, cost, and carrier to
determine all possible flight plans for a person wishing to travel between two different cities
serviced by an airline (assuming a path exists). For each of these possible itineraries, you will
also calculate the total cost and time incurred.
So we are all on the same page, let me define some terms with the hopes that I will stay
consistent through the remainder of the write up.
● Originating City – Where the flight will be starting from
● Destination City – Where we are trying to get to
● Itinerary – A set of flights that start at originating city and end in destination city
● Leg – one flight that is part of an itinerary.
There will be two input files.
Origination and Destination Data – This file will contain a sequence of city pairs representing
0-stop flights that can be used in preparing a flight plan. For each of these, the file will also
contain a dollar cost for that leg and a time to travel. For each pair in the file, you can assume
that it is possible to fly both directions.
Requested Flights – This file will contain a sequence of origin/destination city pairs. For each
pair, your program will determine if the flight is or is not possible. If it is possible, it will output
to a file the flight plan with the total cost for the flight. If it is not possible, then a suitable
message will be written to the output file.
The names of the two input files as well as the output file will be provided via command line
Consider a requested flight originating in Detroit with the destination of Fresno. From Figure 1,
we can see that there is a direct flight, a flight that goes through Chicago (with 2 legs), and even
longer paths like Detroit -> Austin -> Billings -> El Paso -> Greensboro -> Fresno (5 legs).
We can think of the complete set of flights between different cities serviced by our airlines as
an undirected graph. In Figure 1, a line from one city to another indicates at least one
bi-directional flight path between the cities. In other words, if Cities A and B are connected,
that means there’s a flight from A -> B and a flight from B -> A. Of course, more than one
airline could service flights between those cities. The price and flight time is the same for both
directions for a particular airline. If we wanted to travel from El Paso to Chicago, we would have
to pass through Detroit. This would be a trip with two legs and one included layover. Of course,
it is possible that there is no way to get to a particular destination city from a particular
In forming a flight plan from a set of flight legs, one must consider the possibility of cycles. In
Figure 1, notice that there is a cycle involving Chicago, Fresno, and Greensboro. In a flight plan
from city X to city Y, a particular city should appear no more than one time. No one wants to fly
in a circle like that…