Question 1. Your program should start by reading in the data-file, cities.txt, that has been provided.

This file contains a set of several hundred major cities, along with their longitude and latitude, in degrees. Your program should create a weighted graph structure: in the graph, each vertex stores a single city, and cities that are less than 2000 miles apart are connected to one another by edges, representing a direct flight between the cities, where each edge also has a weight equal to the distance between the cities. For distance calculations, we will use the Haversine Formula, which can take in two points on the globe and give the distance between them.

You should write code to do this calculation, returning the distance in miles between two points as a double value. (Note: for this to work, the inputs to any of the trigonometry functions must be in the form of radians, not degrees. All of the methods you need for this calculation can be found in the Math class.)

Question 2. Once the graph is created, the program should prompt the user for pairs of cities. If the two cities are found in the graph, then it should run a version of Dijkstra's algorithm to find the shortest path between them (many of these paths are quite indirect, since the graph assumes that no direct flight of longer than 2000 miles is possible). The code should continue prompting the user for input until they enter "Q" to quit. If the user enters anything that is not a city in the graph, then the process should start again, asking for a new pair of cities.

When it finds a route between the two cities, it should return that route, along with its total length in miles (truncated to an integer value for output purposes).

For precise output format and behavior, see the demonstration videos that were posted with this assignment, or the sample run included with this document.

Question 3. To improve efficiency of the program, you should add some caching to it. That is, if a user searches more than once for a route between one pair of cities during a single run of the program, it should not re-compute that route using Dijkstra's algorithm. Instead, it should save all search results that it has generated as it goes, and if asked for one that it has already performed, simply return that path.