Short Answers

Complete the following problems from the book and include your answers in the file README.lab11 that you will submit with the lab.

Lab Program

We looked at Dijkstra's Algoritm in class, and today we will try it out on some "real" problems. Recall that Dijkstra's Algorithm computes shortest path in a graph from a single-source to each reachable destination.

In the class shared directory under labs/dijkstra you will find a Java file, Dijkstra.java. This program implements Dijkstra's Algorithm. It reads data from a file whose name is provided as a command line argument. The file contains lines of the form

from_location to_location route_name distance

each of which describes a route from from_location to to_location via route_name over a distance distance.

The program reads in the data, creating a graph. It prompts the user for a start location and a destination location, then computes a solution and reports back the shortest path.

I also have included two data files: sc-map contains data about the Unified Science Center (minus Physics, for some reason), and interstate-highways contains data about roads in the United States.

What to Do

1. Try out the program on the two data files. Compute shortest paths and distances between some of your favorite rooms in the Science Center (the Mac lab is surely one of them) and between some of your favorite cities in the United States (Williamstown is surely one of them).
2. Check out the source code. Make sure you understand how the program works. In a couple of paragraphs, describe what the program does and how. How would you describe the Possibility data structure that this program uses to keep track of the paths?
3. It seems kind of silly that this program builds the graph, computes one path, then terminates. Modify the program so it reads the initial graph, then goes into a loop, prompting the user for commands. Implement this set of commands, initially:
   • help: prints a help message listing available options.
   • quit: terminate the loop and exit the program.
   • places: print a list of all places (graph vertices).
   • from <place>: print a list of all places you can get from <place>, with the name of the route and the distance.
   • trip <place1> <place2>: compute and print out the shortest path from <place1> to <place2> as computed by Dijkstra's algorithm.

   You may wish to break some of the provided code out into other methods or even other classes at this point. Since it is certainly possible to introduce bugs, you should test your program on several routes to make sure you get the same answers as the original program.

4. The shortest route from Williamstown, Massachusetts, to Albuqueruque, New Mexico, spends a lot of time on I-70. Suppose you wanted to avoid I-70 between Indianapolis, Indiana, and St. Louis, Missouri. Perhaps you have learned of a major construction project near Terre Haute, or maybe you just think I-70 is boring.

   Modify your program to include a new command remove <place1> <place2> that removes the direct route between <place1> and <place2>. Keep in mind that this program uses a directed graph and that you want to avoid using the path in both directions after issuing this command.

   Use this new feature to compute a new path that does not use I-70 between Indianapolis and St. Louis. What is the length of the new shortest path?

5. Suppose you travel regularly between Dallas, Texas, and Denver, Colorado. What is the shortest path, using the roads in our database? It probably looks something like this:

   
   Map generated by http://www.randmcnally.com

   There has been a proposal to build a 692-mile interstate highway (I-32) from Dallas to Denver, which would take a route more similar to this:

   
   Map generated by http://www.randmcnally.com

   Implement a new command add <place1> <place2> <via> <length> that inserts a new between <place1> and <place2> along a path named <via> with length <length>.

   You understand that if you want this road to be built, you need to convince congressmen from states other than just Texas and Colorado to approve the funding. Use your program to find two paths which start and end in other states which would be shortened significantly by the construction of Interstate 32. The ends of your two paths should be in four different states. Include the paths both with and without Interstate 32.

6. Suggest two enhancements to this program that would make it more useful to potential travellers. What changes would be needed to the data file and to the program to get your ideas to work? If you would like to implement one or both of these for extra credit, ask in lab for approval, and put a note in your README.lab11 file to describe your extra credit features.

What to Turn In

Turn in a file lab11.tar which contains README.lab11 in which you answer the questions above, and your version of Dijkstra.java that includes your enhancements.