CIS 11: Data Structures & Algorithms

Project N (Optional)

Implement Dijkstra's shortest-path algorithm as described in Chapter 15 of the text, pp 755-766.

• Files in the project:
  • testGraph.cpp, graphShell.h and graphShell.cpp: These files furnish a user interface for the testing of your implementation of Dijkstra's algorithm.
  • graph.h and graph.cpp: The graph class presented here implements a weighted digraph
  • dijkstra.h and dijkstra.cpp: The djikstra class provides for the computation of the distance and predecessor arrays for a given graph and starting vertex. You must provide the calculate() function. dijkstra.cpp is the only file you will submit.
• Testing:
  • theFile.txt provides a representation of the graph presented on page 756 of the text. Use it for testing. The graphShell class assumes that an input file has that name.

When you're satisfied with the implementation, submit your work via the CATE form for Project N.

2005/05/14