# 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

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

• 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? – D.W. Dec 17 '13 at 8:14
• 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. – Connor Tumbleson Dec 17 '13 at 12:43
• Is this graph directed or undirected? Update your question with the answer – smac89 Dec 17 '13 at 15:23

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