CPSC250A Assignment 10000 - Shortest Path

Due Friday December 9

Details

Write a program that reads a list of undirected, unweighted, graph edges from a file and prints the shortest path between all pairs of nodes. If there is no path between two nodes, it should not print anything for the pair. Each line of the edge file is the text label for a node in the graph. Pairs of lines in the file are the edges in the graph. Note, not all pairs are edges. For example, the first and second lines of the file are an edge in the graph, the third and fourth lines are an edge in the graph, but the second and third lines are not an edge. Also note, the file may contain duplicate edges, but only one edge can be between two nodes. The program should:

• read the name name of the edge file as a command line argument.
• use an adjacency matrix to store the graph.
• calculate the shortest path of each pair of nodes with breadth first search, using either a loop or recursion.
• not use the STL string class.

The following is an example input file:

Roanoke
Charlottesville
Charlottesville
Washington DC
Washington DC
Richmond
Charlottesville
Richmond

For the graph:

The program output for this file might look like:

Roanoke - Charlottesville: 1
Roanoke - Washington DC: 2
Roanoke - Richmond: 2
Charlottesville - Washington DC: 1
Charlottesville - Richmond: 1
Washington DC - Richmond: 1

Be sure to test your code on multiple examples and on the cs server.

Submission

Tar your code in a file that contains your name and submit it on the course Inquire site.