Computer Science 211
Data Structures

Mount Holyoke College
Fall 2009

Lab 9: Dijkstra's Road Trip
Due: 4:00 PM, Tuesday, December 15, 2009

For the final lab assignment, you will have a chance to work with some realistic highway routing data to compute shortest driving distances between places. This is a simplified version of the kinds of computations done by your favorite online mapping programs. You will also be able to map the routes you compute using a Google Maps mashup.

You may work in groups of two or three on this assignment. Groups must be formed by Tuesday, December 8, 2009.

The Data

The datasets we will work with come from the Clinched Highway Mapping (CHM) Project (, managed by Timothy Reichard. This site allows travelers to keep track of a plot the highways they have traveled. It started with the U.S. Interstate highway system, but has since been expanded to encompass the entire U.S. Highway system, several state highway systems, and some highway systems in Canada and Europe.

The CHM data consists of a set of points and latitute/longitude coordinates for each highway. We will use a pre-processed form of this data. For each highway system we will work with, the data has been combined into a single file that will allow much easier construction of a graph representation of that system. The first line of this file contains two integer values: the number of places represented in the file (often intersections, sometimes "shaping points" used to make the routing more accurate), and the number of connections between those places (roads). In your graph representation, these will be the numbers of vertices and edges, respectively. The next section of the file specifies the places (vertices), one line per line. Each line contains a string for the place name, and two doubles for the latitude and longitude, in degrees, of the point. The last section describes the connections, again one per line. Here, each line has two place sequence numbers (according to the order each was listed in the place/vertex listing), followed by a string which describes the road (usually a route number) connecting these places.

Two data sets are provided initially. One is relatively small: it is the Provincial Highway system for the Yukon Territory (canyt.gra). The second is much larger: the State Highway system for New York (usany.gra). Additional systems will be processed and made available soon.

Your Tasks

Your tasks are to read the data for a highway system and to be able to do some operations on that data: list the places, list the connections/roads, and compute the shortest path between a pair of places. For the list of places and the shortest path, your program should be able to print the information to the screen or write it to a file suitable for plotting with Google Maps.

To get you started, a class to manage latitude/longitude pairs (LatLng) is provided in its entirety. Also provided is a skeleton of the main driver class (Mapping) that takes care of prompting for commands. The bulk of your work will be to fill in the missing methods in that class. This will include the construction of your graph representation and the computation of shortest paths.

The files to be plotted on maps should contain a list of points, one per line, containing the label and coordinates:

@YT1:BC/YT@YT1:BC/YT (59.999726,-132.11699)
@YT1:+X01 (60.006453,-132.125874)

Details about how to display your plottable output files in my Google Maps application will be made available soon.


Here are some things to keep in mind as you design and implement your solution.


When you're finished, please submit by email to jteresco AT, your well-documented source code for all Java classes required to run your program. Indicate clearly in the comment at the top of your program the names of all group members, and which group members made which contributions to the functionality each file. Also be sure to acknowledge the startup code or any example code (like the book's Dijkstra' Algorithm implementation) that you make use of.


This lab assignment is graded out of 30 points. As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments (use Javadoc!), including your name and a general description at the top of the file, a description of each method with pre and postconditions where appropriate. Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

Grading Breakdown

Program design 4 points
Program style 3 points
Program documentation 6 points
Graph construction 4 points
Listing connections 1 point
Listing points 1 point
Mapping points 1 point
Compute shortest path 6 points
Listing shortest path 2 points
Mapping shortest path 2 points

The program design grade will be based on the design choices you make in your implementation. The program style grade will be based on code formatting and approriate use of Java naming conventions. The program documentation grade is, of course, based on the comments you provide (including Javadoc and pre and postconditions as appropriate). The program correctness grade is based on how well your program meets the functionality requirements. All group members will be assigned the same grade.