To receive full credit it is important that solutions are done neatly, stapled and handed in on time.

From text: K.A. Berman and J.L.Paul, Fundamentals of Sequential and Parallel Algorithms.

Page 318

Exercise 8.16(a)

Pages 443-446

Exercises    12.8, 12.9, 12.17, 12.23

Write a C++ program using Visual C++ that inputs a weighted digraph and computes its weighted distance matrix D using the Bellman-Ford Algorithm. For convenience assume vertex set V = {0, 1, ..., n-1}. Implement the digraph using its weighted adjacency matrix A = (a_ij), i.e., a_ij = weight (length) of edge (i,j) or 0 if there is no edge having tail i and head j. The easiest way to input the digraph is to first input the number n of vertices and then input the edges, where each edge is represented by three numbers i, j, w denoting the tail, head, and weight of the edge, respectively. Your program should output both the weighted adjacency matrix A and the weighted distance matrix D.

You are expected to use good programming style and technique, e.g., use descriptive variable names and proper indentation, properly comment the source code and document the output, use modular design, etc. Submit an electronic copy to the TA, and hand in a hard copy of your program (together with the written part above on the due date) including the source code and attached output for the sample digraph on page 309 and a digraph of your own choosing.