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

  • 3
    $\begingroup$ What kind of performance do you need? Have you thought about using BFS or a modified version of BFS? $\endgroup$ Dec 24, 2014 at 18:39
  • $\begingroup$ I need it to work for $O(N \log{N})$ at most $\endgroup$
    – milos
    Dec 27, 2014 at 16:49
  • $\begingroup$ Is $N$ the number of vertices in $G$? $\endgroup$ Dec 27, 2014 at 23:40
  • $\begingroup$ 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? $\endgroup$
    – knok16
    Jul 26, 2015 at 17:00
  • $\begingroup$ How large is the set $S$? $\endgroup$
    – Kittsil
    Aug 25, 2015 at 4:41

1 Answer 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.