Exercise #8, section 3.2, chapter 3 from Foundations of Algorithms:

Implement Floyds algorithm for the Shortest Paths problem 2 (Algorithm 3.4) on your system, and study its performance using different graphs.

Note: You should output the distance array D, the path array P and the shortest paths. Test your implementation using (1) the test case given in class and (2) your own test cases including digraphs with non-negative edges only and digraphs with some negative edges.

From the book:

Algorithm 3.4:

Floyds Algorithm for Shortest Paths Problem: Compute the shortest paths from each vertex in a weighted graph to each of the other vertices. The weights are nonnegative numbers. The shortest paths are also created

Inputs: A weighted, directed graph and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [i] [j] is the weight on the edge from the ith vertex to the jth vertex. Outputs: A two-dimensional array D, which has both its rows and columns indexed from 1 to n, where D [i] [j] is the length of a shortest path from the ith vertex to the jth vertex.

Additional outputs: an array P, which has both its rows and columns indexed from 1 to n, where P[i][j] is the highest index of an intermediate vertex on the shortest path from v_i to v_j, if at least one intermediate vertex exists. P is 0 if no intermediate vertex exists.

Algorithm 3.4:

void floyd2 (int n, const number W[][] , number D[][], index P[][]) index, i, j, k; for (i = 1; i