4. For a certain directed graph with 4 vertices, Floyd's Algorithm has produced the following arrays...

Transcribed Image Text:

4. For a certain directed graph with 4 vertices, Floyd's Algorithm has produced the following arrays D(3) and P(3). Using these values, compute the missing values in the arrays D(4) and P(4), Show how you computed. D(3) 1 2 3 4 1 0813 2 16 0 7 9 9 17 0 2 6 3 7 0 3 4 a) (3 pts) D4 [1] [2] = b) (3 pts) D(¹4)[2][3] = c) (3 pts) P(4) [2] [3] = d) (3 pts) P(4) [3][2] = P(3) 1 2 3 4 0003 3003 0 1 0 0 00 10 12 3 4 D(4) 1 2 3 1 0 1 2 15 09 3 5 0 8 4 6 3 7 0 00 439 2 p(4) 1 2 3 4 1 0403 2 40 3 3 4 00 4 0 010 e) (5 pts) Using the array P(4), find the path from v, to v₂ that is shortest. Show how. you apply the information in P(4) to arraive at your answer. f) (3 pts) True or False: In general for a directed graph with n vertices, the Floyd's Algorithm guarantees that for all vertices v₁, vj, Vk, D() [i][j] =D() [i][k] + D(n) [k][j] 4. For a certain directed graph with 4 vertices, Floyd's Algorithm has produced the following arrays D(3) and P(3). Using these values, compute the missing values in the arrays D(4) and P(4), Show how you computed. D(3) 1 2 3 4 1 0813 2 16 0 7 9 9 17 0 2 6 3 7 0 3 4 a) (3 pts) D4 [1] [2] = b) (3 pts) D(¹4)[2][3] = c) (3 pts) P(4) [2] [3] = d) (3 pts) P(4) [3][2] = P(3) 1 2 3 4 0003 3003 0 1 0 0 00 10 12 3 4 D(4) 1 2 3 1 0 1 2 15 09 3 5 0 8 4 6 3 7 0 00 439 2 p(4) 1 2 3 4 1 0403 2 40 3 3 4 00 4 0 010 e) (5 pts) Using the array P(4), find the path from v, to v₂ that is shortest. Show how. you apply the information in P(4) to arraive at your answer. f) (3 pts) True or False: In general for a directed graph with n vertices, the Floyd's Algorithm guarantees that for all vertices v₁, vj, Vk, D() [i][j] =D() [i][k] + D(n) [k][j]