Solution for QID #21711: Consider an undirected graphG= (V, E).Ghasnnodes representin | StudyHelpMe

Consider an undirected graph G = (V, E). G has n nodes representing cities and m edges representing roads. Each road e ∈ E has an associate length le > 0. There is a proposal to add one new road to this network, and there is a list of E′ of pairs of cities between which the new road can be built. You are asked to determine the road e′ ∈ E′ whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.