copyright Steve J. Hodges   http://steveh.net/cs21/cs21-hw09.html

CS21 Spring 2018

Assignment 9

Extra Credit: Graph Algorithm

Directory Name

21-9

Required Executable Name

p9

I'll run your program either way:
./p9
java p9

Program Description

Implement the Floyd-Warshall graph algorithm. Display the final distance and parent matricies.

Input

Read, from STDIN, the complete set of directed edges, one edge per line. Source node, Destination Node, and Weight for that edge will be integers separated with a comma, and/or whitespace, and given in that order. Nodes will be identified by contiguous integers starting at 1. The number of nodes can be infered from the highest index to be identified by an edge.

Output

Output, to STDOUT, a nicely formatted final distance matrix and a parent matrix. Rows and Colums must be properly aligned and labeled. Your output line length need not be limited by the terminal line width—larger output will be redirected to a file.

Sample Input

1 8 5
1 11 2
1 1 12
5 4 -2
1 3 11
1 10 8
12, 8, 10
12, 11, 8
12, 7, 6
6, 5, -3
12  9, 4
12,2  1
12,5,9
6,7,-1

What to turn in

Put all of the source code files (.cpp, .h, makefile if approprite, .java, etc.) but no executeables, binaries, compiler, or data files (omit .o, "a.out" , .class files etc.) in a folder named as shown above in the home directory of your account on pengo. Please don't include any sub-folders.