Zip file with source files, documentation, &c.
Browsable version of the files above
In this homework, you'll be implementing a general graph
class, and then implementing two separate algorithms for
finding shortest paths in graphs:
The core of this assignment is the GeneralGraph
class, which implements the Graph interface. The
graphs we are dealing with are
In previous assignments, such as the queue, hashtable, and priority queue, there was not much choice in how to implement the interface we gave you. This assignment is a bit more open-ended; we give you the interface for the graph, but there are many possibly ways of implementing it. You should look over the Graph interface and understand it well before starting on your graph implementation.
Ideally, your implementation should be:
Of course, there are tradeoffs, and you should think about what representation will do best overall.
Since you have already written your own implementations of many of the more interesting data structures, there are no restrictions on which classes in the Java standard library you may use.
Your first task, once your graph class is working well, is to implement Dijkstra's shortest-path algorithm. The algorithm should stop as soon as it has found the shortest path from the start vertex to the end vertex, and it should return the list of edges in the path (from that list, the vertices in the path as well as the cost of the path can both be found pretty easily).
Of course, Dijkstra's algorithm does not work in all cases on graphs with edges of negative weight; as you've seen, Dijkstra's algorithm can fail on such graphs, and your implementation should throw an IllegalArgumentException if it is given a graph with a negative-weight edge. However, our graph class allows such edges, so we will also implement a less efficient algorithm that succeeds in such cases: the Bellman-Ford algorithm.
Your implementation should run in time O((|V|+|E|)\log(|V|)), including the cost of the operations inside the graph class.
Note: You CANNOT use Java's Priority Queue for this assignment. You must write your own!
The interface for the Bellman-Ford algorithm is exactly the same as with Dijkstra's algorithm; it should behave the same way, except that it should give correct results on graphs with negative-weight edges as long as there are no negative-weight cycles. Your implementation should throw an IllegalArgumentException if the graph it is given contains a negative-weight cycle.
Your implementation should run in time O(|V|*|E|).
The Graph interface takes two generic types. V is a type for vertices; there are no restrictions on it --- you can choose any class you want in the vertices of your graphs. E is the type for edges, but there are certain restrictions: we must, at the minimum, be able to ask an edge for its source vertex, destination vertex, and weight. Therefore, E must extend the Edge class.
The shortestPath function is a function that uses generics, even though its class doesn't. Specifically, it takes V (the type for vertices) and E (the type for edges, which must extend the Edge class) as parameters, and operates on a Graph<V,E>. Even though it uses generic types, you can call the function normally (as if it didn't use generics at all): Java will figure out what types it must use for V and E.
You may want to read the Java generics tutorial for a more complete reference; section 5 discusses generic methods.
It should go without saying that your submission must have good style. This is needed so that the TAs can understand your code and give you partial credit. It's also a good habit.
In the file theory.txt there are some theory questions. Please answer the questions in this file and submit it along with your .java files.