0
$\begingroup$

So, I have a list of cities (A, B, C, etc) with weighted edges (two-way, undirected) between them with a list of cities that already have a store.

My task is to place a one new store at either A, B, C, etc so that I minimize the travel distance from any city to a store.

So my head is thinking

  1. Perform Dijkstra's on every non-city vertex
  2. Find the max distance among that node -> all other nodes.
  3. Store that distance associated with the store it originated from.

The problem I encountered was

The easiest example of A, B, and C cities with a store already existing at A, has roads of AB = 1, BC = 2.

Placing a store at B, would make C have to travel 2 units to the nearest store (at B). While placing a store at C, would make B have to travel 1 unit (since it can backtrack to A where a store is at).

This "backtracking" to other nodes is causing my mix-ups. Since I'm only iterating from the point of view of either City B or C. B's point of view thinks the max distance to a store is 2, while C does as well. (Even though C should find the max value of 1 unit).

Improve this question
$\endgroup$
3
  • $\begingroup$ How many new stores do you have to place? Just one? Multiple? If it's just one, why not try each of the possibilities in turn? $\endgroup$
    – D.W. ♦
    Commented Dec 17, 2013 at 8:14
  • $\begingroup$ Correct one store. My mistakes I think were trying to modify Dijkstra's, when I could just complete it then iterate through the nodes looking for shorest path to a store. $\endgroup$
    – Connor Tumbleson
    Commented Dec 17, 2013 at 12:43
  • $\begingroup$ Is this graph directed or undirected? Update your question with the answer $\endgroup$
    – smac89
    Commented Dec 17, 2013 at 15:23

1 Answer 1

Reset to default
1
$\begingroup$

Hint: If you have all-pairs shortest-paths information, and if you are considering placing a store at city X, can you compute the max distance from any city to a store? You could now enumerate all possibilities for city X. What's the running time of this algorithm?

An alternative approach:

Hint: If you add a new source vertex and add edges from it to _______, and then use Dijkstra's algorithm to compute single-source shortest-paths starting from that source, does that give you any useful information that will help you? (You'll have to fill in the blank somehow.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I enumerated all possibilities after placing a store and all seems to work. Took a few times to tweak, but it works. I believe the running time is big O( e + n lg n), since I used a queue. $\endgroup$
    – Connor Tumbleson
    Commented Dec 18, 2013 at 15:36

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.