Selecting k "special" nodes in a graph such that the min distance is maximized?
Assuming $k$ is part of the input, the problem is NP-hard (by reduction from Independent Set; there's an independent set of size $k$ if and only if there's a way to solve your problem and achieve a minimum distance of 2 or greater).

Your current plan is known as the furthest-point heuristic.  It's a heuristic, because it won't necessarily give the optimal solution, though often it gives a solution that's reasonably good.  The furthest-point heuristic has been used, among other things, as a technique to select the initial values for $k$-means clustering.

If you want to find an exact solution, you could express this as an instance of of ILP or SAT.  Suppose we want to test whether min-distance $t$ is achievable.  For each variable $v$, you have a boolean variable $x_v$ that's 1 if $v$ is selected or 0 otherwise.  Now for each pair of nodes $u,v$ such that $d(u,v)&lt;t$, you add a constraint saying that you cannot choose both $u$ and $v$ (e.g., the constraint $x_u+x_v \le 1$ or $(\neg x_u \lor \neg x_v)$).  Finally, you add a constraint that exactly $k$ nodes much be selected, and then you test whether these constraints are satisfiable.  If they are, min-distance $t$ is achievable.  Now repeat using binary search to find the largest $t$ such that the instance is satisfiable.