5. (12 points total) Let G = (V,E) be a complete digraph on |V| = n...

 

Transcribed Image Text:

5. (12 points total) Let G = (V,E) be a complete digraph on |V| = n vertices indexed from 1 to n. Thus for any pair of distinct vertices i and j in V, there is an edge (i, j) in E. Assume that each edge (i, j) in E has an associated nonnegative weight w(i, j). For any i and j in {1,..., n}, let f(i, j) denote the maximum weight of any simple directed path from vertex i to vertex j. (Remark: Thus f(i,i) = 0 for all i in {1,..., n}.) The all-pairs longest path distances (APLPD) problem asks us to compute f(i, j) for all i and j in {1,..., n}. Bob wants to create a polynomial-time algorithm for the APLPD problem. He proposes the following variant of the Floyd-Warshall all-pairs shortest paths algorithm. 1: procedure BOB (G) for 1 to n do for j1 ton do if i = j then Xij 0 2: 3: 4: 5: 6: else 7: xijw(i, j) 8: end if 9: end for 10: end for 11: for k 1 ton do 12: for 1 to n do 13: 14: 15: 16: 17: 18: for j1 ton do if i j then Tij+max(2i_j, nh thi) end if end for end for 19: end for 20: end procedure In each of the following parts, prove or disprove whether the stated claim is guaranteed to hold (for all G) upon termination of Bob's algorithm. (a) (6 points) For all i and j in {1,..., n}, we have xij f(i, j). (b) (6 points) For all i and j in {1,. ,n}, we have xij f(i, j). 5. (12 points total) Let G = (V,E) be a complete digraph on |V| = n vertices indexed from 1 to n. Thus for any pair of distinct vertices i and j in V, there is an edge (i, j) in E. Assume that each edge (i, j) in E has an associated nonnegative weight w(i, j). For any i and j in {1,..., n}, let f(i, j) denote the maximum weight of any simple directed path from vertex i to vertex j. (Remark: Thus f(i,i) = 0 for all i in {1,..., n}.) The all-pairs longest path distances (APLPD) problem asks us to compute f(i, j) for all i and j in {1,..., n}. Bob wants to create a polynomial-time algorithm for the APLPD problem. He proposes the following variant of the Floyd-Warshall all-pairs shortest paths algorithm. 1: procedure BOB (G) for 1 to n do for j1 ton do if i = j then Xij 0 2: 3: 4: 5: 6: else 7: xijw(i, j) 8: end if 9: end for 10: end for 11: for k 1 ton do 12: for 1 to n do 13: 14: 15: 16: 17: 18: for j1 ton do if i j then Tij+max(2i_j, nh thi) end if end for end for 19: end for 20: end procedure In each of the following parts, prove or disprove whether the stated claim is guaranteed to hold (for all G) upon termination of Bob's algorithm. (a) (6 points) For all i and j in {1,..., n}, we have xij f(i, j). (b) (6 points) For all i and j in {1,. ,n}, we have xij f(i, j).

Answer rating: 100% (QA)

a To prove or disprove that for all i and j in 1 n we have xij fi j we need to consider the correctn... View the full answer