Q)a)] (T/F) Given graph G = (V,E), if E = O(V), then Floyd-Warshalls all-pairs shortest path algorithm runs as fast as johnsons algorithm

b)

(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):

for (u,v) ? E

Set w(u,v) = (w(u) + w(v)) /2 + w(u,v)

Run Johnsons algorithm on G, w to compute the distance d(u,v) for all u, v ? V

For u, v ? V

Set d(u,v) = d(u,v) + (w(u) + w(v))