Overview: In this project you will use Dijkstra's algorithm to find route information between two airports chosen by the user. The user will be shown a route that results in the lowest price. Details: Create a class called Dijkstra. The structure of this class in terms of inner classes and methods will be up to you. Points will be reduced if your program is not well organized and commented. Basic requirements are: 1) Input a file airports.txt that contains the graph in adjacency list form. 2) Performs the Dijkstra algorithm on the graph to create shortest path information. 3) Prints the shortest path information between two airports chosen by the user. 4) Repeats until the user chooses to exit. Notice that in this case "shortest" means "cheapest". You are expected to write Dijkstra's algorithm yourself following the pseudocode found in the slides. You may not use code for Dijkstra's algorithm found from other sources. Your output should match the sample output below: Sample output: Enter departure airport: DFW Enter arrival airport: SFO Price: 1100 Connections: 1 Route: DFW -> LAX -> SFO Check another route (Y/N)? 

airports.txt:

ATL BOS 250 DFW 250 MOB 59 AUS DFW 59 HOU 59 SAT 59 BOS ATL 250 DFW 250 DFW ATL 250 AUS 59 BOS 250 HOU 128 LAX 1000 LIT 59 MSY 128 OKC 59 SHV 59 SFO 1200 HOU AUS 59 DFW 128 SAT 59 LAX DFW 1000 SFO 100 LIT DFW 59 MOB ATL 59 MSY DFW 128 OKC DFW 59 SAT AUS 59 HOU 59 SFO DFW 1200 LAX 100 SHV DFW 59 

Dijkstra Dijkstra's Algorithm The algorithm proceeds in stages. If a linear scan of the vertices is used to find the vertex of least cost, this step takes O(VI) At each stage, it selects a vertex which has Since the loop processes each vertex for O(IVD the smallest distance among all the time, then O(VP) time is required. unknown vertices. The inner update loop takes OCED since the It then declares this vertex known, updates update is constant time. the table for the adjacent vertices if the cost So, the running time is OGIE IVI2) is less than the current cost, and repeats this again for the next least distance vertex, until If the graph is dense so that E OOIVP, then the all vertices are known. algorithm is linear in the number of edges. Dijkstra If the graph is sparse, with El O(IVI), then the algorithm is too slow. It can be improved by using a priority queue for getting the next cheapest cost vertex. Removing each vertex is odogIVD The edge updates require a OGlogIVD "decreaseKey" for each edge over the course of the algorithm. So, the running time is find next min edge updates OIVI log IV El logIV OOEl logIVD Dijkstra Dijkstra's Algorithm The algorithm proceeds in stages. If a linear scan of the vertices is used to find the vertex of least cost, this step takes O(VI) At each stage, it selects a vertex which has Since the loop processes each vertex for O(IVD the smallest distance among all the time, then O(VP) time is required. unknown vertices. The inner update loop takes OCED since the It then declares this vertex known, updates update is constant time. the table for the adjacent vertices if the cost So, the running time is OGIE IVI2) is less than the current cost, and repeats this again for the next least distance vertex, until If the graph is dense so that E OOIVP, then the all vertices are known. algorithm is linear in the number of edges. Dijkstra If the graph is sparse, with El O(IVI), then the algorithm is too slow. It can be improved by using a priority queue for getting the next cheapest cost vertex. Removing each vertex is odogIVD The edge updates require a OGlogIVD "decreaseKey" for each edge over the course of the algorithm. So, the running time is find next min edge updates OIVI log IV El logIV OOEl logIVD