Back to lab index

15-200
Lab 11 - Driving Directions: Finding the Shortest and Quickest Routes

Due: Monday, November 21, 2005

Overview

This assignment asks you to build your own MapQuestTM-like product. Basically, your software should read a map for the user and determine the shortest and fastest ways of going from one place to another.

The input to the program should be a map file, a the starting city and the destination city. The output of the program should be two routes from start to finish -- one indicating the route with the shortest travel time adn the other the route with the shortest length. The two might be different if, for example, a short road thorugh a city is heavily congested but a longer suburban route is high-speed and unobstructed. Each route should show each city along the way as well as the time or mile marker for that city.

The Map

The map file is a simple plain-text file containing three sections:

We have provided code that will create two graphs, represented as adjacency lists, from this map file. It is contained within the constructor of the RoadMap class. We have done our best to make this code insensitive to whitespace issues, but we recommend that your map files look like our sample files -- this will help to keep things readable.

As a matter of convenience, we included both the source and destination verticies within the Edges stored within the adjacency lists. We did this becuase it simplified the code. This did, of course, waste a good bit of space. A more space-efficient implementation would most certainly only include the destination vertex, since the source vertex is the index into the list.

We have provided only the simplest among test maps. You should really create much more complex and interesting examples for testing. Please turn in your test cases -- you will be graded, in part, on the completeness of your test set..

Your Piece of the Pie

We tried to provide code for all of the dry or essoteric parts of the assignment leaving you only the interesting pieces. In particular, you should complete the following:

Provided Code