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