# Computing the $k$ Nearest Neighbors for all Vertices via Dijkstra

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.

PDF.