3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ It's too obvious... and slow... There must be a better solution, as it's a contest problem. $\endgroup$ – milos Jan 7 '15 at 15:06
  • $\begingroup$ It is too slow for $N = 10^5$. $\endgroup$ – beginner1010 Oct 24 '15 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.