Suppose we are given a weighted graph $G=(N,E)$ ($W(e)$ is the weight corresponding to $e\in E$). Let $d(i,j)$ denote the minimum weighted distance between nodes $i$ and $j$.
My goal is to split the graph into disjoint components ($B_1,\ldots,B_K$) s.t. $\max_{i,j\in B_k}d(i,j)<a$ for some given constant $a>0$ ($d(\cdot,\cdot)$ here is the distance on $G$) and the resulting partition minimizes $K$ (i.e. the total number of components).
Of course, I can perform an exhaustive search. However, for a sufficiently large graph it seems to be infeasible. Is there a clever way to find such partition?
Clarification: My ultimate goal is to create a partition s.t. the number of elements in each component is as large as possible (given the constraint) while the variation of $|B_1|,\ldots,|B_K|$ is minimized ($|B_k|$ is the size of $B_k$).