COMP 410 Fall 2015

Part 3: Dijkstra's Shortest Path Algorithm


Summary

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.


Input format

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_source
There 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.


Output and Format

  1. First, print out a line with about 40 "#" characters in a row. This will help visually separate solutions if the input file contains multiple graphs.

  2. Next, print out the graph using the format from part 1.

  3. Next, print a blank line.

  4. Finally, print the shortest path information you have computed, using both node numbers and node names (text) in this format: 
     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.

Miscellaneous Notes