Dijkistra Graph Program. Would appreciate if someone can help me with this program in Java. I pasted the dat files in the bottom.

1. Understand Single-source shortest paths problem.

2. Understand Dijkstras Algorithm.

3. Develop a directed graph data structure based software.

Overview:

Develop an interactive software for city and route queries.

Project Description:

This software is a menu driven graph application that solve problems such as finding the shortest paths between two cities, city information inquiry, add and delete route between the two cities chosen by user.

Functional Requirements:

1. The software builds a directed graph by reading the information from two resource files:

a. 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.

b. 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.

2. User menu:

a. Q: Query the city information by entering the city code. In this option, user will be asked to enter the letter Q first. Then the software will ask for city code in a new line. User will then enter the city code. Error handling requirements (see Functional Requirements section) apply. Upon successful input, the software displays the city information (the whole record) on screen..

b. D: Find the shortest distance between two cities. In this option, user will be asked to enter the letter D as the command. Then the software will ask for city codes in a new line. User will then enter two city codes in one line, separated by one space. Error handling requirements (see Functional Requirements section) apply. Upon successful input, the software must display a user-friendly result with detailing the distance and the route on screen.

c. I: Insert a road by entering two city codes and distance. In this option, user enters letter I as the command. The software will ask for two City Codes and the Distance, all in one line, separated by one space. Error handling requirements (see Functional Requirements section) apply. Upon successful input, the software must report the result to user on screen.

d. R: Remove an existing road by entering two city codes.

In this option, user is asked to enter the letter R for command. Then the software will ask for two City Codes. User will enter them in one line, separated by a space. Error handling requirements (see Functional Requirements section) apply. Upon successful input, the software must report the result to user on screen.

e. H: Display this message. In this option, the software display a set of command to help user. Details refer to section Expected Results.

f. E: Exit.

In this option, user enter the letter E to exit the software.

3. User can enter commands repeatedly without exiting the software.

Engineering Requirements:

1. The software must be implemented in Java language.

2. The software must be written from scratch and use minimum Java library. Use excessive Java library will impact the points of this project you will get.

3. Create a Java Digraph (directed graph) class to store the city and road information.

4. The software must use Dijkstra Algorithm to find the shortest path between two cities.

5. Output: The entire user/software interaction is to be displayed on the Command Prompt only.

6. Output file isnt required for this project.

7. Addition and Removal of a road must follow directed graphs definition.

8. Distance between the two cities should be integer, not double.

9. Command must be one letter. Any other characters such as multiple letters, numbers, special characters or combination of any them arent accepted.

10. The software shall not exit unless user chooses to.

11. Error handling: The software must handle errors correctly and gracefully.

If users input doesnt conform to the requirement, the software should display a message that will guide user to enter them correctly the next time.

If the resources files cant be read, a proper warning message must be displayed and the software should exit.

Scope

1. Generic type support isnt required.

2. Use only Dijkstras algorithm for finding shortest paths.

3. Use the command line for user to provide information the software required.

4. Commands can be either a upper case or lower case letter.

Expected Results

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

Testing Guidance

Expectations:

1. All test cases mentioned below are tested.

2. The software should not crash while running the test cases mentioned below.

Test cases

1. Pick 4-5 cities, draw a graph, then manually apply Dijkstras algorithm so you can have some reference to test your result. I recommend the first 5 cities.

2. Create two smaller resource files using the above picked 4-5 cities by extracting these cities information from city.dat and road.dat, test your software with the manual algorithm application results. You can add one option to the user menu to pick which resource files you want the software to read. The later is optional but can save your time of testing.

3. After you are satisfied with your smaller set of datas results, run the software with the big files as-is.

4. Test invalid input as command:

Wrong command: numbers, multiple letters, upper case letters, lower case letters.

Command and Data arent in one input line.

Command and Data arent separated by one space.

Correct command letter and wrong data.

5. Results testing:

Q: city code doesnt exist.

D:

1. The road doesnt exist between two cities (remember this is a directed graph).

2. One of the city code doesnt exist.

3. Repeating the same query sequentially.

I:

1. Insert a road and then query it by using Q command.

2. Insert a road already existed.

3. Insert a road between two non-existing cities.

4. Insert a road between one existing and one non-existing cities.

R:

1. Remove road and then query it by using D command.

2. Remove a non-existing road.

3. Remove a road that was removed already by a user.

4. Remove a road between two non-existing cities.

5. Remove a road between one existing and one non-existing cities.

H: Help display

E: exit.

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

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