CPSC250A Assignment 10000 - Shortest Path

Due Friday December 9


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:

The following is an example input file:

Washington DC
Washington DC

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.


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