Minimum shortest path cover of $n$ vertices in $R^m$
Without further assumptions about the point set, the answer can be anywhere between $1$ and $n/(k+1)$.


Lower bound: Consider the 1-dimensional point set in which $v_i = 2^i$.  For every  index $i &gt; 1$, the nearest neighbor of $v_i$ is $v_{i-1}$.  So the directed $1$-nearest-neighbor graph can be covered by a single shortest path $v_n \to v_{n-1} \to\cdots \to v_1$.
Upper bound:  Consider the 1-dimensional point set where
$$v_i = n^2 \lfloor i/(k+1) \rfloor + (i\bmod (k+1)).$$  This point set consists of $n/(k+1)$ tight clusters of $k+1$ points, with large gaps between the clusters.  The $k$ nearest neighbors of any point $v_i$ are in the same cluster as $v_i$.  Thus, the $k$-nearest-neighbor graph has $n/(k+1)$ components.  It follows that we need at least  $n/(k+1)$ shortest paths to cover the graph.