In this third part you will use your basic graph data structure from part 1 to solve a graph problem. Write a Java program that implements Dijkstra's shortest algorithm. The algorithm will compute on a connected directed graph with weights on the edges. It will find the shortest path from a single source node to each other node in the graph.
Your Java program will read the graph information from a text file named "p3graphData.txt". Please make sure that is the file your program opens and reads from, as that is the name of the file we will use when grading.
The format is this:
s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_source //==================== s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_source //==================== s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_sourceThere is one edge per line. Each edge (line) has a source node name (si), a destination node name (di), and an edge weight (wi, which will be a positive integer). The line that is "-1" signals the end of the graph structure input. The line after that will contain one of the node names, which will be used as the single source node for Dijkstra's algorithm.
Note that we allow more than one graph to be defined in the input file. Each graph will have the same format, and they will simply follow on e another with the "//====================" line tossed in between them for visual separation as you edit test text files.
Here is an example:
Raleigh Durham 14 Durham Hillsborough 9 Chapel_hill Graham 25 Chapel_hill Carrboro 1 Carrboro Cary 32 Cary Raleigh 3 Pittsboro Cary 17 Pittsboro Sanford 15 Sanford Los_angeles 3012 -1 Pittsboro //==================== N1 N2 1 N2 N3 1 N3 N1 1 -1 N1
This file contains two graphs. This means your program will compute the shortest path information for each one, one at a time.
Each node name will be a single string with no blanks in it, and the three items on a line will be separated by one or more blanks. Each line will have zero or more blanks before the first node name.
We will work with connected graphs, so the only nodes in the graph are the nodes named in the edges. You may wish to read the input file twice... once to collect all node names (and make those parts of your graph data structure) and then a second pass to create the edges.
Shortest Paths from source node (7) Pittsboro to: (0) Raleigh: 20 (Raleigh, Cary, Pittsboro) (1) Durham: 34 (Durham, Raleigh, Cary, Pittsboro) (2) Hillsborough: 43 (Hillsborough, Durham, Raleigh, Cary, Pittsboro) (3) Chapel_hill: no path (4) Graham: no path (5) Carrboro: no path (6) Cary: 17 (Cary, Pittsboro) (7) Pittsboro: 0 (Pittsboro) (8) Sanford: 15 (Sanford, Pittsboro) (9) Los_angeles: 3027 (Los_angeles, Sanford, Pittsboro)Note that we have the node number in parens, then the node name, a colon and the path length; then the entire path is printed in parentheses, using node names, comma separated. We show the path here in reverse order since that is easiest to do recursively; if you wish to print it in forward order feel free to do so.