Figure 2 shows the contents of 4 and 4 , the distance and predecessor matrices after the fourth iteration, when the Floyd-Warshall all-pairs shortest path algorithm is applied to a weighted directed graph D.

(a) Compute the contents of the distance matrix, 5 , and predecessor matrix, 5 .

(b) Give the sequence of vertices in full shortest path of the round trip from vertex 2 to vertex 4 and back to vertex 2. Also, list all the edges traversed along each path with the weight of each edge in the order in which they are traversed along the shortest path for the round-trip. What is the shortest distance of the round trip from vertex 2 to vertex 4 and back to vertex 2?

(c) Add directed edges to the graph in Figure 3 so that it represents a graph that is minimal with respect to edges that generates the distance and predecessor matrices in (a).

(d) If possible, generate a topological ordering of the digraph D, drawn in (c) such that when there are two or more choices of the vertices to be selected, the choice is based on the lexicographical ordering of the valid choices. If it is not possible, give a reason why the topological ordering of the vertices of D is impossible.

3. Figure 2 shows the contents of A and II4, the distance and predecessor matrices after the fourth iteration, when the Floyd-Warshall all-pairs shortest path algorithm is applied to a weighted directed graph D 0 5 6 2 3 5 0 2 7 8 A43 8 05 6 7 12 4 0 1 1 3 5 3 0 0 1 4 1 4 114=131014 Figure 2: Distance and Predecessor Matrices (a) Compute the contents of the distance matrix, A5, and predecessor matrix, IT5. [10 points] (b) Give the sequence of vertices in full shortest path of the round trip from vertex 2 to vertex 4 and back to vertex 2. Also, list all the edges traversed along each path with the weight of each edge in the order in which they are traversed along the shortest path for the round-trip. What is the shortest distance of the round trip from vertex 2 to vertex 4 and back to vertex 2? [5 points] (c) Add directed edges to the graph in Figure 3 so that it represents a graph that is minimal with respect to edges that generates the distance and predecessor matrices in (a). [5 points] 3. Figure 2 shows the contents of A and II4, the distance and predecessor matrices after the fourth iteration, when the Floyd-Warshall all-pairs shortest path algorithm is applied to a weighted directed graph D 0 5 6 2 3 5 0 2 7 8 A43 8 05 6 7 12 4 0 1 1 3 5 3 0 0 1 4 1 4 114=131014 Figure 2: Distance and Predecessor Matrices (a) Compute the contents of the distance matrix, A5, and predecessor matrix, IT5. [10 points] (b) Give the sequence of vertices in full shortest path of the round trip from vertex 2 to vertex 4 and back to vertex 2. Also, list all the edges traversed along each path with the weight of each edge in the order in which they are traversed along the shortest path for the round-trip. What is the shortest distance of the round trip from vertex 2 to vertex 4 and back to vertex 2? [5 points] (c) Add directed edges to the graph in Figure 3 so that it represents a graph that is minimal with respect to edges that generates the distance and predecessor matrices in (a). [5 points]