Suppose I have a graph $G$ (possibly with weights on edges), and I have a subset $S$ of $k$ vertices $s_1, \dotsc, s_k$. I want to solve the post office problem: that is, I want to partition the vertices of $G$ into subsets $D_1, \dotsc, D_k,$ so that $s_i$ is the closest vertex of $S$ to every vertex in $D_i.$ I assume this has been studied - what is the most efficient algorithm?
$\begingroup$
$\endgroup$
6
asked Apr 2, 2020 at 14:45
-
$\begingroup$ Add a new root node $r$ connected with $s_1,\ldots,s_k$ with edges of weight $1$, say. Then find a minimum weight spanning tree $T$ with root $r$ using Dijkstra's algorithm, for example. Given any node $n$ the path from $n$ to $r$ in $T$ will lead to the nearest post office at the next to last step. $\endgroup$– François G. DoraisCommented Apr 2, 2020 at 15:03
-
2$\begingroup$ Dijkstra on an augmented graph is the right call, but its output is not a minimum weight spanning tree but a shortest path tree. $\endgroup$– Ben BarberCommented Apr 2, 2020 at 15:22
-
$\begingroup$ @BenBarber Indeed. For some reason I hadn't heard of the shortest path tree. If you want to make this an answer, I am happy to accept. $\endgroup$– Igor RivinCommented Apr 2, 2020 at 17:25
-
$\begingroup$ @BenBarber Thanks for the correction! A minimum weight spanning tree would also work, but Dijkstra's algorithm is quick and to the point. $\endgroup$– François G. DoraisCommented Apr 3, 2020 at 2:54
-
$\begingroup$ @FrançoisG.Dorais, I'm not sure that's right: if everywhere is 2 from the root but 1 from each other then a minimum spanning overestimates the distance to almost everywhere. $\endgroup$– Ben BarberCommented Apr 15, 2020 at 13:50
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Once you decide that the elements of $S$ should look for the vertices in their part rather than the other way round the naive approach of exploring edges one at a time in increasing distance from $S$ is the best you can do (up to administrative overhead) because you might have to examine all of the edges anyway. This is essentially Dijkstra's algorithm.
answered Apr 15, 2020 at 14:09