HW4: Dijkstra's Algorithm

• To develop good test cases for a computational problem (and for an algorithm, described in pseudocode, that solves it).
• To translate pseudocode for an algorithm into a working implementation.
• To work with an Updatable Priority Queue.
• To deeply understand Dijkstra's Algorithm, which solves the Single-Source Shortest-Paths problem.

To do this assignment, you will do the following steps in order.

1. Make a new Java class: Dijkstra.
2. Read the pseudocode for Dijkstra's Algorithm, and discuss it with your partner to understand it.
3. In a comment at the top of your Dijkstra.java file, write answers to a few questions about the algorithm.
4. Copy the Java interface code for the method ssspDistances().
5. Write a stub body for ssspDistances(), just to get it to compile.
6. Design several test cases on paper.
7. Implement those tests in the main method of the Dijkstra class. Keep in mind that, to run a test, you should print out a description of the meaning of the test, the expected output, and then the actual output that the function produced.
8. Write your implementation.
9. Repeat the previous five steps for the method shortestPaths().

Your work will be evaluated based on the quality of your tests, the correctness and robustness of its implementation (that is, whether it gets the right answer for a variety of inputs, including tricky edge cases), and the organization and style of your code. There is also a small extension that counts for two points (shortestPaths()).

It's likely that you will want to refer to the Javadoc documentation for our class's ADT interfaces and implementation classes.

Download all the ADT and implementation code from the page for the graph traversal activities.

This is a partner assignment. Work with your assigned partner from class and submit only one copy of your work. As always, all partners' names should be in a comment at the top of the source code, and you should work by pair programming. No working remotely! You need to be sitting side by side.

Create a new Java file Dijkstra.java with the empty class Dijkstra defined within it. Note that only static methods (and static final fields) are allowed: your class should store no mutable state! Here's a sketch of what it should look like once you're done:

// HW4: Dijkstra's Algorithm
// By Thelma Dickinson and Louise Sawyer
// For Data Structures: Comp 630, 10th period, with Dr. Miles
// S'16 at Phillips Academy
// 
// Due 2016-04-26

// ...
// ... [ Answers to questions about Dijkstra's algorithm; step 3 above ]
// ...

public class Dijkstra {
    /**
     * ... [ Javadoc comment for ssspDistances() ]
     */
    public static List<Double> ssspDistances(WeightedGraph G, int source) {
        // ... [ Stub body at first, then implementation filled in later ]
    }
    
    /**
     * ... [ Javadoc comment for shortestPaths() ]
     */
    public static List<List<Integer>> shortestPaths(WeightedGraph G,
                                                    int source) {
        // ... [ Stub body at first, then implementation filled in later ]
    }
    
    // ... [ Helper functions for methods above ]
    
    public static void main(String[] args) {
        // ... [ Tests for ssspDistances() ]
        // ... [ Tests for shortestPaths() ]
    }
    
    // ... [ Helper functions for your tests ]
}

Obviously there should be no notes in square brackets in the code that you submit to me, nor ellipses. Those are simply placeholders for work that you will do throughout the assignment.

In a weighted graph, the “length” of a path in a weighted graph is the sum of the weights of the edges along that path. A “shortest $s–t$ path” is a path from $s$ to $t$ whose length is the minimum out of all $s–t$ paths. The “distance” from $s$ to $t$ is this minimum length, or ∞ if no path exists.

The Single-Source Shortest Paths problem (SSSP problem) is the following task: given a single starting node $s$ in a weighted graph, compute the distance from $s$ to each node in the graph.

There are several variations on this problem. An upgraded version instead asks us to compute a shortest $s–v$ path for all $v$ in the graph, rather than just the length of this path. The algorithm below can be upgraded to solve this problem instead, and in fact that's what you'll do for shortestPaths() at the end of the assignment.

In addition, a more limited version of the problem specifies two vertices, $s$ and $t$, and asks just for a shortest $s–t$ path, or just the length of this path. This is trivial to solve by first solving the entire SSSP problem, and then looking up the answer just for $t$.

Given an unweighted graph (directed or undirected) $G = (V,E)$ with non-negative weighting function $w$, and a vertex $s$ in that graph, the Single-Source Shortest Paths problem is solved by Dijkstra's Algorithm:

Read and discuss this algorithm with your partner. Take a while to think through why it works, and what each part means. Relate it to the more abstract pseudocode we went over in class. Then answer the following questions in a comment at the top of Dijkstra.java.

1. How is this algorithm different from BFS and DFS? How is it similar?
2. Could we instead use BFS or DFS to solve the shortest-path problem? Why or why not?
3. How do we know that this algorithm will terminate?

You will implement the above algorithm in a method with the following signature:

/**
 * Computes single-source shortest path distances.  Given graph G and vertex
 * s, computes the length of the shortest path from s to each node in G.  G
 * is a weighted graph, but may be directed or undirected.
 * 
 * @param      G The graph in which to search.
 * @param source The ID of the node from which distances will be computed.
 * 
 * @return A List of length G.numVerts(), whose entry at index u is the
 *         distance from source to u.
 */
public static List<Double> ssspDistances(WeightedGraph G, int source)

1. Copy that method interface and fill in a stub body, just enough to get it to compile. (In particular, in this case you should just immediately return an empty list.)

2. Before you write your implementation, design a thorough set of tests on paper.

   Keep in mind that a test consists of an input, an expected output, and, when executed, a comparison to the actual output computed by the implementation. Note that you can and should write your tests before you write your implementation.

   Working on paper, try to come up with example graphs that will demonstrate the different expected behaviors of the algorithm, and also come up with challenging graphs that might expose bugs. (Remember that big things are challenging for humans, but usually not for computers! Your goal is to come up with devious examples, not necessarily big or complex ones.) Think about edge cases — empty graphs, singletons, fully disconnected graphs, graphs with many connected components, trees, complete graphs, etc. Don't bother testing invalid input; that's not the point.

3. Implement your tests in code to run from the main method. When run, each test should print out the following three things:

   • A very brief explanation of the idea you're testing / the situation that you've constructed to test
   • The expected output
   • The actual output of the call to ssspDistances()

   Use spacing and indentation in your printed output so that the output is as easy as possible to read, and so that tests are easy to distinguish from each other. A giant pile of hard-to-decipher text is not helpful to your users, and will not earn full credit.

   You may write helper functions for your tests; in fact, for graph algorithms this is a particularly good idea, since there's so much verbose code just to create the graph. (Messy code will also not earn full credit.)

   When you first run your tests, it's likely that they'll all fail, since you haven't yet implemented the algorithm. That's just fine!

4. Now fill out your implementation of ssspDistances(), as always using descriptive variable names and comments. Use your tests as a guide to catch bugs.

For your final two points on this assignment, test and implement another function, with the following interface:

/**
 * Computes single-source shortest paths.  Given graph G and vertex s,
 * computes a shortest path from s to each node in G.  G is a weighted
 * graph, but may be directed or undirected.
 * 
 * @param      G The graph in which to search.
 * @param source The ID of the node from which distances will be computed.
 * 
 * @return A List of length G.numVerts(), whose entry at index u is a list
 *         of vertices forming a path from source to u.  If no such path
 *         exists, the list for u is empty.
 */
public static List<List<Integer>> shortestPaths(WeightedGraph G, int source)

1. Copy the method interface and fill in a stub body.
2. Design a thorough set of tests on paper.
3. Write your tests into your code to run from the main method.
4. Write your implementation of shortestPaths().

Submit your Dijkstra.java file on Canvas. (Only one submission per pair!)

Start early, ask lots of questions, and have fun!

This assignment is worth 25 points.