Consider an undirected graph G = (V, E)

Subject:Computer SciencePrice:2.89 Bought3

Share With

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