[Solved]: all pairs shortest path using Dijkstra

Problem Detail: 

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).

Asked By : Connor Tumbleson

Answered By : D.W.

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19048