CSC 365- Programming project 4 --(Due December 9th, 2005)

Part1 -- Weighted Graph Class

graph was designed to represent a graph where there are no weights assigned to edges; the ShortestPath method finds the path with the least number of vertices between a source and a destination.

Develop a weightedGraph class where edges have an enumerated weight associated with them. this will involve adding a double field to the adjacent node class that represents the weight of an edge. The methods insertEdge, outEdges, and findsp must be updated to reflect this change. In findsp, when comparing cp against sp, it should be the total weight of the two paths that are compared and not the number of edges in each.

Update the test1 and test2 programs for testing your weightedGraph class.

Part II -- Improving Shortest Path Algorithm's Performance

The findsp method that I wrote and you updated in part1 finds the shortest path between two nodes; however, with about 1000 nodes and a few thousand edges between them, it takes this algorithm a significant amount of CPU time to find the answer.

Your job is to research algorithms that improve the performance of findSP and implement your finding. You must provide a well-defined definition of the algorithm and document where you found the algorithm; you will then need to implement the algorithm you found and compare and contrast its performance against the one that I have provided for you.

For comparing the original against your updated versions of findSP, it may be best to have both the original and the updated approaches to finding SP in the same weightedGraph class. Your test program should be set up to get SP in two or more ways for the same graph and the same source and destination.

test2.java has time calculation code already built into it. Obviously, you need to set up a similar program to test your weightedGraph initially. You can then modify it to test the affect of your modifications. Incrementally trying both your updated and original versions with more nodes and edges; keep track of the elapsed times in each case.

What to hand in

• The definition of the algorithm you used to improve findSP and your source.
• Your implementation of it in the context of our weighted graph class; as mentioned earlier, it may be best to embed the original and your version of findSP in the same weightedGraph class.
• Develop a report documenting your efforts even if they provided no improvements. Your test results must support anything that you say; any sentences that start with I feel ..., I am sure that ..., It is obvious that ... are probably not going to help your case. Include the following in your report:
  1. Description of what you changed and why you believed those changes would improve performance.
  2. Tabulation of the timing information drawn from the testing of the two versions.
  3. Highlight the performance improvements that were achieved, if any. If your changes show improvements in some cases, make clear what those cases were, the reasons for the improvement, and why your changes did not cause improvements in others.