Problem 2: [20 pts] (Floyd-Warshall algorithm) Let G = (V, E) be the directed weighted graph...

 

Transcribed Image Text:

Problem 2: [20 pts] (Floyd-Warshall algorithm) Let G = (V, E) be the directed weighted graph shown below with its asso- ciated weighted adjacency matrix. Solve the all-pairs shortest-path problem on this graph by running the Floyd-Warshall algorithm Recall that in the Floyd-Warshall algorithm (1) where di = wij so D = W, and D is the matrix [d]. Show the matrix Di, where i = 1, 2, 3, 4, 5, 6, 7, 8, 9 and D is the final solution. h W = = d = min{dk, d +dk=} 5 a a -3 d 5 -2 e -2 i f 4 3 bo a b C 0 b 0 g C -200 d -3 e 0 3 888 3 9 5-2 h 8 i 5 6 9 d e f g h i 7 1 7 6 9 1 0 5 b 888-8887 -2 1 f 0 0 0 3 0 -2 Problem 2: [20 pts] (Floyd-Warshall algorithm) Let G = (V, E) be the directed weighted graph shown below with its asso- ciated weighted adjacency matrix. Solve the all-pairs shortest-path problem on this graph by running the Floyd-Warshall algorithm Recall that in the Floyd-Warshall algorithm (1) where di = wij so D = W, and D is the matrix [d]. Show the matrix Di, where i = 1, 2, 3, 4, 5, 6, 7, 8, 9 and D is the final solution. h W = = d = min{dk, d +dk=} 5 a a -3 d 5 -2 e -2 i f 4 3 bo a b C 0 b 0 g C -200 d -3 e 0 3 888 3 9 5-2 h 8 i 5 6 9 d e f g h i 7 1 7 6 9 1 0 5 b 888-8887 -2 1 f 0 0 0 3 0 -2