This Java program implements a graph data structure. Create a Java Digraph (directed graph) class to store the city and road information. Use Dijkstra's algorithm for finding the shortest distances between cities.

Input: Two files - one contains city data and the other contains road data.

> city.dat: This file contains information about cities, where each line has 5 attributes: City Number, City_Code (2 letters), Full_City_Name, Population, and Elevation.

> road.dat: This file contains information about roads, where each line has 3 attributes: From_City, To_City, and Distance. Note that all roads are assumed to be one-way.

Output: A menu driven system which has the following options.

Read the original data files and store the data to appropriate data structures. Let the user of this program enter a City Code and your program should print out the cityinformation (the whole record). Find the connection between two cities. - The user will be asked to enter two City Codes. The program finds the shortest distance between the two cities. Insert a road (edge) between two cities - The user will be asked to enter 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. Delete a road (edge) - The user will be asked to enter two City Codes for a road. Note that if the road entered doesn't exist, print out a warning message. Exit.

Your program should resemble the following output (the user inputs are bolded): % java Project 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

Input files:

city.dat

road.dat

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