Graph Algorithms

Introduction

We have provided a class called Graph that represents an undirected weighted graph. You will implement a class called GraphSolver, which is a wrapper around a Graph providing implementations of Breadth-First-Search and Dijkstra's algorithm.

Specification

Please see the JavaDoc here.

Additional Remarks

• Begin by reading the Javadoc for the Graph class. The class you are writing (GraphSolver) relies on this one.
• Be sure that you understand the contracts for the methods doDijkstra, getShortestPath, and getShortestDistance:
  • We expect the user to invoke the doDijsktra method before either of the other two. The doDijkstra method will perform Dijkstra's algorithm, storing the results in some instance variables.
  • The methods getShortestPath and getShortestDistance should be quite short! They will access the results that were computed previously when doDijkstra was invoked.
• You may use the constant Integer.MAX_VALUE to represent "infinity" in your implementation of Dijkstra's algorithm. (You may assume that there will not be any weights that are this large.)

Testing

Look at the Public Tests to get an idea of how to write tests for this project. You can rely on the Graph.createGraph method to instantiate a Graph<String> using information contained in a text file. The text file will contain one line for each edge in the graph. For example, the graph depicted at the top of this page is described by the text file publicTestGraph.txt. It looks like this:

A B 5
B C 7
C A 50

You should create some more sophisticated graphs and write your own tests that rely on them.

Grading

• Public tests: 21%
• Release tests: 79%

Web Accessibility