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!

  • $\begingroup$ Can you edit the question to credit the original source of this exercise? Thanks! $\endgroup$
    – D.W.
    Commented Jun 12, 2018 at 22:55

1 Answer 1


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.

  • $\begingroup$ That's what I thought! The first solution is by far better $\endgroup$
    – alienflow
    Commented Jun 13, 2018 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.