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?



Voronoi diagram on (weighted) graphs
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](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).


