Lab 3: route finding

Deadlines: first deadline 12 December, final deadline 21st December.

In this lab, you will implement Dijkstra’s algorithm for finding the shortest path between two nodes in a weighted graph, and try it out as part of a graphical route planner.

Implementing Dijkstra’s algorithm

Start by downloading the file Graph.java, and take a look at the code. The class is intended to implement Dijkstra’s algorithm for undirected weighted graphs, in which the nodes are labelled by strings and the weights are integers. If you look at the code, you will see that not much has been written yet.

Your job is to complete the code, by implementing the following methods:

The constructor Graph() creates an empty graph.
addVertex(label) adds a node with the given label. You may assume that the node does not already exist in the graph.
addEdge(node1, node2, dist) adds an edge with weight dist between the nodes node1 and node2. You may assume that the two nodes exist in the graph and that dist is non-negative.
shortestPath(start, dest) returns a Path object that represents the path from start to dest having the lowest total weight (if there are multiple such paths, it returns one of them). If there is no path from start to dest, the method must return null. You may assume that the two nodes exist in the graph.
(The local class Path represents a path between two nodes in the graph. A Path can be created by using its constructor, which takes two arguments: totalDist is the sum of the weights of all edges in the path (i.e., the total weight), and vertices is the list of nodes which occur in the path, in the correct order, including the start and end node. You do not need to modify the code in Path.)

You should use adjacency lists to represent the graph, although the exact details are up to you. Your implementation of shortestPath should use Dijkstra’s algorithm and have O(n log n) time complexity or better, where n = |E| + |V| is the number of edges plus nodes in the graph. You will therefore need to use an efficient priority queue.

You must explain why your implementation of shortestPath has O(n log n) time complexity. Write this down in a file complexity.txt and include it with your submission.

Hint: if your complexity analysis results in O(n² log n) complexity, this may mean that your code is correct but the analysis is not precise enough. You probably have an inner loop that loops over some edges. Think about how many edges this inner loop processes throughout the entire run of Dijkstra’s algorithm; this tells you how many times the loop runs in total.

You can use anything you want from Java’s standard library. In particular, you may find the PriorityQueue class helpful. You may also use your priority queue from lab 2 if you want. If you use a HashMap in your code, you may assume that the hashing operations take O(1) amortised time.

Here is an example which shows how the Graph class should behave:

Graph g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addEdge("A", "B", 2);
g.addEdge("B", "E", 3);
g.addEdge("A", "D", 7);
g.addEdge("D", "E", 1);
g.addEdge("B", "C", 1);
System.out.println(g.shortestPath("A", "C"));  // totalDist: 3, vertices: [A, B, C]
System.out.println(g.shortestPath("D", "A"));  // totalDist: 6, vertices: [D, E, B, A]
System.out.println(g.shortestPath("E", "F"));  // null

Programming hints

Here are a few programming hints that may help you solve the lab:

You will most likely need to define a class that represents a single entry in the priority queue.
Keep your solution simple! You should be writing well under 100 lines of code, so before adding a new class, think if you really need it.
When you are in the phase of Dijkstra’s algorithm that computes the distance to each node, don’t try to calculate the full path to each node (though it may be helpful to record each node’s predecessor in the path). Only once you have computed the distance to the target node should you think about finding the path.
You can reverse an ArrayList using java.util.Collections.reverse.

You can iterate through all the key-value pairs in a Map like so:

Map<String, Integer> myMap = ...;
for (Map.Entry<String, Integer> entry: myMap.entrySet()) {
    String key = entry.getKey();
    int value = entry.getValue();
    // Now do whatever you want with key and value
}

Testing

There is a test program which tests your implementation of Dijkstra’s algorithm. To use it, download the following files:

You can then run the test program as follows:

java TestDijkstra dijkstratestcases.txt

The test program is good at finding bugs; make sure to use it.

Debugging hints

If the test program finds a bug in your code, it prints out Java code which exhibits the bug. Your first step should probably be to take this code and add it to Graph.java as a main method. Then you can start debugging the code to work out why it doesn’t work. Here are some hints for how to do that.

Start by running your new main method, and printing out the distances computed by your algorithm, as well as the predecessor nodes if you are using them in your solution. Are they correct? Check carefully! If they are correct, the bug must be in creating the Path object; if they are wrong, the bug is in the earlier part of Dijkstra’s algorithm.

If the distances computed are wrong, your next goal is to find out which iteration of the loop caused the failure. Try printing out the contents of your data structures after each loop iteration, and find the first point where the data structures are not as you expect. Here it is important to think extra carefully about what you expect to see after each loop iteration!

Now you have isolated the first loop iteration where your algorithm went wrong. By using a similar approach (printing things out, checking them carefully for correctness) you should be able to pinpoint the exact point where the failure occurred.

If you are using a Java IDE, you can use the built-in debugger to step through the execution of the program and look at your data structures at each point. Depending on your personal taste, this may be more convenient than printing out values. For instructions on how to do this using Eclipse, see here or here. Note: you should not attempt to run the debugger on TestDijkstra.java; this leads to weird things happening. Instead, copy the failing test into your own code and run it from there.

A route planner

In this part, you will try out your implementation of Dijkstra’s algorithm by using it as a route planner. You do not need to do any extra programming to use the route planner. The route planner GUI is already implemented for you and looks like this:

To use the route planner, start by downloading the following files:

You will also need to download a route map. This consists of two files, one which lists all the bus/tram stops and one which lists the bus/tram lines. If you download maps.zip, you will get the following maps:

stops-air.txt and lines-air.txt. This is a small graph from an earlier course book.
stops-g332.txt and lines-g332.txt. This is graph 9.8 from Weiss.
stops-gbg.txt and lines-gbg.txt. This is a (somewhat out-of-date) travel map of Göteborg.
stops-bvs.txt and lines-bvs.txt. This is a big graph with many stops and lines, which you can use to check that your solution works efficiently.
stops-nopath.txt and lines-nopath.txt. This is an unconnected graph, which may be useful for testing your implementation.

To run the route planner, you need to have compiled both GUIMain.java and Graph.java, and to have Lab3Help.jar in the current directory. When you compile GUIMain.java, you will need to add Lab3Help.jar to your CLASSPATH like so:

javac -cp .:Lab3Help.jar GUIMain.java

or on Windows:

javac -cp .;Lab3Help.jar GUIMain.java

Then, to try out the map of Göteborg, run the following command:

java -cp .:Lab3Help.jar GUIMain stops-gbg.txt lines-gbg.txt

or on Windows:

java -cp .;Lab3Help.jar GUIMain stops-gbg.txt lines-gbg.txt

(If you are using Eclipse or similar, you will need to add Lab3Help.jar to your CLASSPATH.)

Then choose two stops and click the button to see the best route between them. You can of course replace stops-gbg.txt and lines-gbg.txt with whichever map you want to try out.

You should try out your implementation of Dijkstra’s algorithm on a few different routes, and make sure that it produces the right answer. It is probably a good idea to start with the smaller graphs, such as stops-air.txt/lines-air.txt, and work your way to the bigger ones. You should also check that your algorithm works efficiently by trying it on stops-bvs.txt/lines-bvs.txt, which is a big graph.

Submission

Submission is through Fire. You should submit all the code you’ve written, as well as the file complexity.txt.

Before you upload your code to Fire, you should make sure that your program works correctly. The test program should run correctly, and you should also try to test your program using the route planning GUI.