# 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? Dec 24, 2014 at 18:39
• I need it to work for $O(N \log{N})$ at most Dec 27, 2014 at 16:49
• Is $N$ the number of vertices in $G$? Dec 27, 2014 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? Jul 26, 2015 at 17:00
• How large is the set $S$? Aug 25, 2015 at 4:41

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."
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 is too slow for $N = 10^5$. Oct 24, 2015 at 11:19