Consider the following directed graph G. You will compute the transitive closure, G*, of G using the Floyd-Warshall algorithm for k = 1,2,3.

(a) Draw the graphs G1, G2, and G3, generated by the Floyd-Warshall algorithm after the first 3 iterations. (i.e. G1 includes paths through vertex 1, G2 includes paths through vertex 2, etc.)

(b) We do not always need to run the outermost loop n times with the Floyd-Warshall algorithm. Why is that?

 

1 3 2 5 U 4