Q)a)] (T/F) Given graph G = (V,E), if E = O(V), then Floyd-Warshall’s all-pairs
ID: 3712539 • Letter: Q
Question
Q)a)] (T/F) Given graph G = (V,E), if E = O(V), then Floyd-Warshall’s all-pairs shortest path algorithm runs as fast as johnson’s 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 Johnson’s 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))
Explanation / Answer
a) <False>
The time complexity of Johnson's algorithm becomes same as Floyd Warshell when the graphs is complete (For a complete graph E = O(V2).
b) <True>
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.