Aset of cities v is connected by a network of roads g(v, e). the length of road e ∈ e is le. there is a proposal to add one new road to this network, and there is a list e0 of pairs of cities between which the new road can be built. each such potential road e 0 has an associated length. as a lobbyist for for city s, you wish to determine the road e 0 ∈ e that would result in the maximum decrease in the driving distance between s and a particular city t. give an efficient algorithm for solving this problem, and analyze its running time as a function of |v |, |e| and |e0