Recently i have found a problem stating: There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new road to this network, and there is a list E′ of pairs of cities between which the new road can be built. Each such potential road e′∈ E has an associated length. As a designer for the public works department 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.
The basic solution was to apply to 2 times Dijkstra (from s to city x and from t to a city y) and then try all the edges from E' which would result into
2*𝒪(Dijkstra) + 𝒪(|E'|) = 𝒪((|V|+|E|)⋅ log |V|+|E’|)
But then on the web I found an altrenative solution:
If you run Dijkstra for every edge in E’, the running time is 𝒪(|E|⋅|E’|⋅ log |E|)
I do not understand this alternative. Could anybody explain this strategy to me? Thanks in advance!