Pre-Lab Due Tuesday, April 23rd at 11:59 pm
Code and Post-Lab Writeup Due Friday, April 26th at 11:59 pm
In this lab, you will implement Dijkstra's shortest-path computation on a weighted, directed graph, and use the results to return the shortest paths to vertices.
This lab consists of three components:
The pre-lab and post-lab are two separate assignments, due on different days. They should be prepared following the guidelines in the eHomework Guide.
The pre-lab is intended to be completed before the coding component; it will help ensure that you understand the code and can work out an implementation strategy. For this reason, the pre-lab is due earlier than the other two components of the lab.
To succeed at the pre-lab, you need to read the provided code described below and be able to answer basic questions about its methods. These questions are given in the pre-lab document.
Prepare a brief PDF document that answers each of the questions asked in the pre-lab, following the eHomework guidelines. Submit your document to the "Lab 13 Pre-Lab" assignment via Gradescope by its due date.
We've provided you with an implementation of a directed graph and a framework for computing and returning shortest paths in such a graph. Your job for this lab is twofold:
Implement Dijkstra's shortest-path algorithm. Given a graph, a weighting function on its edges, and a starting vertex, compute the length of a shortest path to each vertex, and record the tree of parent edges that make up all such shortest paths.
Reconstruct shortest paths. Given the results of the shortest-path computation (specifically, the parent edges) and a designated ending vertex, compute and return a shortest path from the starting vertex to the ending vertex.
As you know, Dijkstra's algorithm requires a min-first priority queue
to operate. For this lab, you will use the priority queue in from
your Lab 3, which resides in the heaps package in your repository.
The provided code assumes that this package exists in your repo and
contains a working MinHeap class.
If you did not get your
MinHeapclass working in Lab 3, please talk to a TA as soon as possible to ensure that you are able to get it working in order to complete this lab. Not having a working heap will result in your code not passing the tests and not receiving credit.
The directed graph implementation you'll be using is in the spath.graphs
package. A graph consists of vertices, each of which is associated with
lists of incoming and outgoing adjacent edges. Take a look at the
Vertex class to see how to enumerate the edges out of a vertex.
The main code of interest for this lab is in the spath package:
ShortestPaths.java contains the driver for the shortest-paths
algorithm. You'll have to complete the methods of this class to
make your lab work.
VertexAndDist.java contains a class that pairs a vertex and an
estimate of its distance from the start. Your priority queue will
store a collection of these objects -- one per unfinished vertex.
The ShortestPaths class takes in a weighted graph and starting vertex
and does all the work needed to compute shortest paths. To complete
this class, you must finish the implementation of two functions:
The run() function executes Dijkstra's algorithm on the graph.
In particular, it computes a map parentEdges from vertices to
their parent edges in the shortest-path tree computed by the
algorithm.
The returnPath() function takes an ending vertex $u$ and returns
the shortest path from the starting vertex to $u$ that was computed
by run(). It returns this path as a linked list of the path's edges.
For the run() function, we've provided code to fill the priority
queue initially and to set the starting vertex's shortest-path
distance to 0. Take a look at this code to make sure you understand
how to use the VertexAndDist class and the priority queue itself.
You must then fill in the main loop of the algorithm as discussed in
class.
We have provided you with some JUnit tests in TestShortestPath to
help you check that your shortest-path computation works. As always,
passing the unit tests does not guarantee that your implementation is
correct -- you are ultimately responsible for correctness -- but
failing them does indicate that there is a problem you need to fix.
The unit tests construct graphs with known (unique) shortest paths and then compare the paths you return to the known ones. If your path and the correct path diverge, the test will fail and will show you a picture indicating where your path diverges from the correct path.
To complete this portion of the lab, you must do the following:
Make sure your code passes the JUnit tests as we originally gave them to you. Our lab autograder script will use the output of these unit tests as part of the assessment of your code's correctness when grading.
Make sure you eliminate or disable any print statements or other
extraneous code, other than what is needed to implement the lab,
that you may have used for debugging. Extraneous code may slow
down your implementation to the point that our autograder will
fail it for taking too long to run.
Make sure you do a Team/Pull on your repository before attempting to push your code. Remember, pull before push!
You must both commit and push all of your code to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
Please check that your code was pushed by logging into bitbucket.org, clicking on your repository, and viewing the source code to verify that it's the most up-to-date version.
Code that is not pushed to Bitbucket will not be graded, and you will not receive credit for it, even if your local copy is correct. Unless you have an unpushed commit with a timestamp prior to the due date, we will not accept it later, as we have no way to verify that the code was completed prior to the deadline.
The post-lab writeup asks you to reflect on your implementation and to think about possible extensions.
Prepare a PDF document that answers each of the questions asked in the post-lab, following the eHomework guidelines. Submit your writeup via Gradescope by its due date.