(a) Suppose that you are given an instance of the MST problem on a graph G, with
ID: 3841544 • Letter: #
Question
(a) Suppose that you are given an instance of the MST problem on a graph G, with edge weights that are all positive and distinct. Let T be the minimum spanning tree for G returned by Kruskal's algorithm. Now suppose we replace each edge weight w_e by its square w^2_e, thereby creating a new instance of the problem with the same graph but different edge weights. Is it true that T is still a minimum spanning tree for this new instance. If you think it is true, give an explanation; otherwise, give a counterexample. (b) Let G = (V, E) e a directed graph in which every edge has unit length (i.e., length = 1). Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.Explanation / Answer
a) for any 2 real numbers a and b, if a < b, then a2 < b2
Hence, when the weights are squared the ordering of the edges according to their weights does not change. So, the MST obtained by Kruskal's method remains same.
b)
The solution is to use breadth first search beginning from s until t is reached
for each vertex v
v.distance = INFINITY
v.known = false
end-for
for d = 0 to |V|
for each vertex v
if v.known = false and v.distance = d
v.known = true
for each vertex w adjacent to v
if w.distance = INFINITY
w.distance = d +1
w.path = v
end-if
end-for
end
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.