# kth nearest vertex in a unweighted graph

Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex. What algorithm can I use for this problem?

I'm actually thinking of algorithm for finding shortest paths from every vertex to all other vertices (like Floyd-Warshall algo, but in our case graph is unweighted and we need much better performance).

• What kind of performance do you need? Have you thought about using BFS or a modified version of BFS? – James Evans Dec 24 '14 at 18:39
• I need it to work for $O(N \log{N})$ at most – milos Dec 27 '14 at 16:49
• Is $N$ the number of vertices in $G$? – James Evans Dec 27 '14 at 23:40
• What do you mean by "kth nearest vertex"? Is it mean that path beetwen vertexes should contain exact $k$ edges or at most $k$ edges? Or is it related to Nearest neighbor graph? – knok16 Jul 26 '15 at 17:00
• How large is the set $S$? – Kittsil Aug 25 '15 at 4:41

## 1 Answer

Letting $G = (V,E)$, and $|V| = N$, your problem essentially boils down to computing a portion of the shortest path tree for every vertex in $G \setminus S$, where the shortest path tree is truncated after the $k$th "special vertex."

You mention the Floyd-Warshall algorithm; however, that algorithm seems inappropriate here, since it's designed for weighted graphs, and only returns the lengths of the shortest paths between every pair of vertices.

A more natural approach might be to run BFS on every vertex in $G \setminus S$, halting when you reach the $k$th "special vertex." Since you'd be running BFS on every vertex in $G \setminus S$, your worst-case runtime would be $O(N' \cdot |E|)$, where $N' = N - |S|$. (I'm assuming you only want the $k$th nearest special vertex for the non-special vertices.)

You would be able to improve the performance slightly by caching the portions of the shortest-path trees you compute on each call of BFS, but those changes wouldn't shift the worst-case performance. I believe any known shortest-path algorithm will have complexity dependent on $|E|$, so I'm not sure that you could solve this problem in $O(NlogN).$

• It's too obvious... and slow... There must be a better solution, as it's a contest problem. – milos Jan 7 '15 at 15:06
• It is too slow for $N = 10^5$. – beginner1010 Oct 24 '15 at 11:19