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 w2_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.