Homework 11: Due 12/6

Implement Dijkstra's Shortest Path Algorithm, as described in Project 3. Specifically, add a method with the following header to the myWeightedGraph class:

	int[] DSP(String source)

The method DSP takes a source vertex and finds the shortest paths from that vertex to all other vertices. As usual, the shortest paths are represented as a tree rooted at the source vertex using the int [] that keeps track of parents. As in the case of your implementation of Prim's Algorithm for Homework 10, you should use a VertexHeap.

To test and experiment with your implementation, do the following:

  1. Construct by hand 10, connected, edge-weighted graphs, each with 8 vertices and 10-15 edges. Suppose that the vertices are called 1, 2, ..., 8. Also, construct by hand the shortest paths from vertex 1 to all other vertices in the graph. Then input your graphs to your implementation of DSP and confirm that your implementation produced the output you expected.
  2. Repeat the experiments from Homework 10 on random graphs.

Submit a document, called homework11.pdf containing a write-up describing your tests with the 10 small graphs as well as your experimental results with the large random graphs. Your document should contain drawings of the 10 small graphs. It should also discuss the "timing issues" that you discussed with respect to your MST implementation for Homework 10, but this time with respect to your DSP implementation.