all pairs shortest path using Dijkstra 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


Perform Dijkstra's on every non-city vertex
Find the max distance among that node -> all other nodes.
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).
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.)