Project 3 - Shortest Paths

   < Previous  Next >

Objectives:

Description:

Using your project2 code, extend it to calculate the shortest paths from the first vertex in the input file to all other vertices. The syntax for the input file is: 
VERTEX1	VERTEX2	WEIGHT
where WEIGHT is the (positive) cost for to go from VERTEX1 to VERTEX2. An example input file is project3-testA.txt: 
s	t	10
s	y	5
t	x	1
t	y	2
y	t	3
y	x	9
y	z	2
x	z	4
z	s	7
z	x	6

Requirements

Your program needs to meet the the following requirements for full points:
  1. Create a Digraph class (see below for description).
  2. Create your own test input files for various conditions (for example, disconnected graphs) include them with your submission. These files should follow the same syntax as the example (namely, vertices and weights are separated by a TAB character).
  3. Copy and paste the rubric below into a .txt file and indicate a value for each "_____", including the number of hours spent. Include this .txt with your submission.
class Digraph:
This class should store a digraph. Furthermore, this class should contain:
  1. Appropriate constructor(s)
  2. Private data members:
    1. Edge information as either an adjacency matrix or an adjacency list
    2. Number of vertices
    3. Number of edges
    4. Vertex labels
  3. Methods to support adding, removing and printing individual vertex information
  4. A method that implements a shortest path algorithm
Additionally, do not use Swing components (to accommodate the grading pipeline).

Examples

Your program should match the following output exactly: (user input in bold text)
Note, user input is in bold face blue and underlined text is required for test cases. 
Please enter the input filename (or simply press return to use ./project3-testA.txt): project3-testA.txt
Importing vertices, edges (and their weights) from project3-testA.txt . . .

Found 5 vertices and 10 edges in project3-testA.txt
The costs for the shortest path from the first vertex (s):

Vertex	Dist.	Path
------	-----	----
t	8	y, s
y	5	s
x	9	t, y, s
z	7	y, s
Here's another example. Given the input file project3-testC.txt:
z	x	6
z	s	7
x	z	4
y	z	2
y	x	9
y	t	3
t	y	2
t	x	1
s	y	5
s	t	10
a	b	1
a	c	2
b	c	3

then your program should produce input that matches the following: 
Please enter the input filename (or simply press return to use ./project3-testA.txt): project3-testC.txt
Importing vertices, edges (and their weights) from project3-testC.txt . . .

Found 8 vertices and 13 edges in project3-testC.txt
The costs for the shortest path from the first vertex (z):

Vertex	Dist.	Path
------	-----	----
x	6	z
s	7	z
y	12	s, z
t	15	y, s, z
a	Infinity
b	Infinity
c	Infinity

Rubric:

Points      Item
----------  --------------------------------------------------------------
_____ / 10  Style
            + Code is indented correctly
            + Functions should be no longer than 1 page
            + Documentation: (written for another software developer)
              * All source code files include Javadoc header block with description, author, version/date, etc.
              * Javadoc (with block tags) before each method
              * All non-trivial variables are commented
              * Comments included before major portions of code
_____ /  0   Program compiles without errors
_____ /  0   Program executes without crashing
            Requirements met:
_____ / 20  + Class(es) with appropriate methods and data members
_____ / 40  + Output indicates correct results
_____ /  8  + Test files [that you made]
_____ /  2  Completed rubric

_____ / 80  Total


_____  Approximate number of hours spent

I, (REPLACE WITH YOUR FULL NAME), affirm that the code that I submitted is my own work and that I did not receive help that was not authorized by the instructor.

Copy and paste this rubric into a rubric-project3.txt file (not a .docx, .doc nor .rtf file). Think of this as a checklist to ensure that you receive the maximum points possible. For each grade item, fill in your estimate for the grade you deserve. Additionally, include your estimate of how many hours your spent. Lastly, replace, "(REPLACE WITH YOUR FULL NAME)" with your full name to indicate that what you are submitting is entirely your own work.

Submission

To facilitate grading, structure your program so that the following commands will compile and execute it: 
javac *.java
java ShortestPaths
if main() is in a class named ShortestPaths. Otherwise, use: 
javac *.java
java Digraph
If you're putting your code in a package (or if your IDE is), then 
javac *.java -d .
java <package_name>.ShortestPaths
where <package_name> is replaced by the package name used. If this doesn't work, then please comment out the package statement.
Before submitting this assignment, make sure that there are no compilation errors. If there are errors, fix them before submitting. You may need to edit and compile your program multiple times before it compiles successfully. Verify that the output is correct (meaning that every single character matches the output). Once you are able to successfully run the program with the correct output, you are ready to submit the program. To submit multiple files together, first compress a directory into a single .tar.gz or .zip file (e.g., by right-clicking on the folder and choosing send to::Compressed (zipped folder)). (Note, do not submit a compressed file within a compressed file.) Submit your source code and report to the appropriate Assignment tab/folder in CougarVIEW. (Note: Do not submit files with spaces in their names.)

Notes

Optional (worth 0 points!)

  1. Write code that calculates the shortest path from every vertex to every other vertex. Determine the Big-O of your implementation.