33.)

Subject: Advanced Computer Algorithms

State whether the following statements are true or false? Give reasons for your answers.

33. (T/F) Consider the all pairs shortest paths problem where there are also weights on the vertices, and the weight of a path is the sum of the weights on the edges and vertices on the path. Then, the following algorithm finds the weights of the shortest paths between all pairs in the graph: APSP-WITH-WEIGHTED-VERTICES(G, w): 1 for (u, v) E E Set w'(u, v) = (w(u) + w(v))/2 + n(u, v) 3 Run Johnson's algorithm on G, w, to compute the distances 4 for u, v E (u, v) for all u, v E V. Set au, v) =D(u, v) + 2 (n(u) + w(v))