Home Bookmarks Papers Blog

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

Sariel Har-Peled $\newcommand{\Graph}{\mathsf{G}}% \newcommand{\Vertices}{\mathsf{V}}% \newcommand{\Edges}{\mathsf{E}}$
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.

Last modified: Wed Apr 1 22:03:18 CDT 2015