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!

• Can you edit the question to credit the original source of this exercise? Thanks!
– D.W.
Jun 12 '18 at 22:55

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.