In this project you will implement a graph data structure and Dijkstra's algorithm for a practical application. Your program will take in two hard coded input files for input, one representing city data and another representing connection data. a) city.dat -- Number, City_Code(2 letters), Full_City_Name, Population, Elevation. Sorted by the city code. b) road.dat -- From_City, To_City, Distance. City is numbered in the order given in city.dat file.

Output: A menu driven system which has the following options: 1. Read the original data files and store the data to appropriate data structures. 2. Let the user of this program enter a city code and your program should print out the city information (the whole record). 3. Find the connection between two cities. Get two city codes and find the shortest distance between two cities. 4. Insert a road (edge) between two cities -- the user will be asked to enter the two city codes and its distance. Note that if a pair of city codes already exists or if the city code doesn't exist, print out a warning message. 5. Delete a road (edge) -- the user will be asked to enter two city codes for this road. Note that if the road entered doesn't exist, print out a warning message. 6. Exit.

Your program should resemble the following output (the user inputs are underlined): Command? H Q Query the city information by entering the city code. D Find the minimum distance between two cities. I Insert a road by entering two city codes and distance. R Remove an existing road by entering two city codes. H Display this message. E Exit. Command? Q City code: LV 12 LV LEE VINING 8390 5983 Command? D City codes: CH PM The minimum distance between CHINO HILLS and POMONA is 143 through the route: CH, xxx, ..., xxx, PM. Command? I City codes and distance: GG BO 100 You have inserted a road from GARDEN GRPVE to BOSSTOWN with a distance of 100. Command? R City codes: KV MP The road from KERNVILLE and MOUNTAIN PASS doesn't exist. Command? E

city.dat

1 AN ANAHEIM 1273000 310 2 BK BAKERSFIELD 31100 390 3 BO BOSSTOWN 790 10 4 BR BREA CANYON 529000 1242 5 CH CHINO HILLS 52200 1381 6 ED EDWIN DOM 12 8719 7 FI FORT IRWIN 4120 932 8 GD GARDENA 653210 674 9 GG GARDEN GRPVE 913330 952 10 KV KERNVILLE 6530 3925 11 LI LAKE ISABELLA 981 2194 12 LV LEE VINING 8390 5983 13 MP MOUNTAIN PASS 76 7190 14 PD PARKER DAM 2190 1829 15 PM POMONA 698300 298 16 PR PICO RIVERA 189820 1190 17 SB SAN BERNADINO 1293200 1033 18 TR TORRANCE 169400 829 19 VV VICTORVILLE 57460 2190 20 WW WRIGHTWOOD 9234 7910

road.dat

1 19 36 1 4 212 1 2 732 2 9 111 2 1 66 2 12 29 2 19 14 2 17 65 3 2 17 3 11 38 3 14 122 3 17 211 3 1 390 3 18 78 3 9 11 4 3 273 4 5 29 4 12 42 5 4 122 5 16 12 5 20 102 5 9 32 6 5 211 6 1 62 6 8 132 6 12 871 7 11 122 7 2 200 7 13 81 7 4 41 7 1 20 7 14 11 8 6 5 8 3 210 8 16 74 9 2 95 9 11 2 9 7 120 9 20 11 10 12 121 10 20 653 10 3 925 11 2 81 11 12 219 11 4 90 11 16 211 12 19 122 12 8 390 12 5 98 12 7 122 12 3 11 13 9 9 12 17 121 13 17 26 13 1 719 13 20 832 14 20 219 14 10 182 14 9 13 14 3 22 15 6 22 16 11 73 16 18 98 17 20 190 17 1 77 17 11 21 17 12 93 17 9 200 18 10 33 18 16 940 18 8 29 18 20 121 18 15 33 19 2 322 19 5 74 19 6 219 19 10 111