In this lab, you will program Dijkstra's algorithm for finding all shortest paths from a single source vertex in a directed graph. This serves as the foundation of link-state routing. The basic version of this lab just situates Dijkstra's algorithm within a simple program for testing examples such as are in the textbook. However, there is also an extra-credit option that applies the same shortest-path routing principles to a more complicated situation.
You should read and understand DGraph.java, which is the class you will be completing by programming Dijkstra's algorithm. Once you have filled in the missing portion, you can test it out using the program Routes.java, which reads in a textual description of a network (i.e., a directed graph with nonnegative costs on the edges) and writes out a least-cost path from a designated start vertex to each of the vertices.
The input file should begin with the name of the start vertex and then contain a list of directed edges, each of which consists of two vertices and a cost. All items are separated by whitespace. For example, the example network from Kurose and Ross's Figure 4.27, with the example start vertex of u, would be described as in the attached example file. Assuming you have downloaded that file and have the Java code finished and compiled, you could test it out with
java Routes < example
Of course, you should use other test cases as well.
Unless you choose to do the extra-credit alternative, you should just turn in the code of your calculate method.
You can use a slight generalization of the DGraph class to solve one of the problems from the November 3, 2007, ACM North Central North America Regional Programming Contest. The interesting fact about the Octavia Traffic Lights problem is that it is the only problem out of the 9 in the contest that not even a single team in the region solved. If you take on this challenge, you'll need to turn in all your code, since your work won't be entirely confined to the calculate method. If you email me your program, I'll be glad to try running it on the official judging data from the contest.