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).
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).$
