Computing the $k$ Nearest Neighbors for all Vertices via
We are given a directed graph $\Graph = (\Vertices,\Edges)$ with
$n$ vertices and $m$ edges, with positive weights on the edges,
and a parameter $k >0$. We show how to compute for every vertex
$v \in \Vertices$, its $k$ nearest neighbors. The algorithm runs
in $O( k ( n \log n + m ) )$ time, and follows by a somewhat
careful modification of Dijkstra's shortest path algorithm.
This result is probably folklore but since we were unable to find
a reference to it, we decided to write it down.