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