CPSC250A Assignment 10010 - All Pairs Least-Cost Path

Due Friday December 9

Details

Write a program that reads a list of undirected, weighted, graph edges from a file and prints the least-cost path between all pairs of nodes. If there is no path between two nodes, it should not print anything for the pair. Triplets of lines of the edge file define the labels for the endpoints and the weight of the edge. The order of the lines in the edge file is node, node, weight. So, the first and second lines define the endpoints of an edge with the weight on the third line. The fourth and fifth lines define the endpoints of an edge with the weight on the fourth line. The weights of the edges are positive integer. However, the file may contain duplicate edges. An edge's weight is the sum of all duplicate edges read from the edge file. 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 all pairs using the Flyod-Warshall algorithm.
• not use the STL string class.

The following is an example input file:

Roanoke
Charlottesville
121
Charlottesville
Washington DC
117
Washington DC
Richmond
108
Charlottesville
Richmond
72

For the graph:

The program output for this file might look like:

Roanoke - Charlottesville: 121
Roanoke - Washington DC: 238
Roanoke - Richmond: 193
Charlottesville - Washington DC: 117
Charlottesville - Richmond: 72
Washington DC - Richmond: 108

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.