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 at 22:55
up vote 0 down vote accepted

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.

  • That's what I thought! The first solution is by far better – alienflow Jun 13 at 11:58

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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