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 file is a simple plain-text file containing three sections:
- The first section contains a single integer indicating the number of cities in the map.
- The second section contains the names of the cities delimited by newlines or whitespace
- The third section enumerates the roads. Each road is specified by the name of the starting city, the name of the destination city, the length of the road in miles, and then the travel time rounded to the nearest whole hour.
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 because 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:
- public DijTableEntry dijkstra (String start, boolean distanceNotTime)
This method should implement Dijkstra's algorithm. The comments within the provided source code describe its function and paramterization.
- public void printPath (DijTableEntry dijTable, String finish)
This method should print the path, including the milestones or time-markers from start to finish. The output should be well formatted and readable.
- private class DijTableEntry
This class should represent the entries for one vertex in the table used by Dijkstra's algorithm: path, distance and the known flag. An array of these will be used to create the table for Dijkstra's algorithm. This array will be indexed by the vertex number.
- Helper functions and other data structures
You might want to implement other helper data structures and helper methods. For example, you might want an array of city names indexed by city number. This would allow you to easily map between city names and city numbers. You could implement this, for example, as a private class with its own methods or as a stand-alone private data structure and helper methods.
The big hint here is, "Don't be afraid to add more sub-class, members, or helper-methods -- they can make life much easier." But, as always, please don't change the interface (the public methods).
- A main method
Your main method should prompt the user for a map file name and cities. It should then produce and output the shortest and quickest routes. It should be user-friendly.
- Several interesting test maps
This is critical. We want to see the maps that you used to test. Please turn these in. They should be interesting -- containing multiple possible routes between cities and differences between the time and distance maps in terms of the best routes.