Add a road to a network (Graph problem with Dijkstra) 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!
Who knows. You'd have to ask them; that doesn't provide enough details to narrow it down.

If I had to guess, I imagine that perhaps they had in mind that they would do Dijkstra's algorithm once to measure the distance from $s$ to each vertex; then for each candidate edge $(u,v) \in E'$, they would use Dijkstra's algorithm to find the distance from $u$ to $t$ assuming $(u,v)$ has been added to the graph; and use this to find the best edge to add. 

In any case, their alternative solution is considerably slower, so it's a poor choice and should not be used.  It's far faster to use the first solution you listed.