practice080's blog

By practice080, 6 weeks ago, In English

The problem statement is simple:

  • Given a undirected unweighted graph with $$$V$$$ vertex and $$$E$$$ edges, $$$M$$$ ($$$1\leq M\leq V$$$) of the vertex are special vertex. For every vertex, find the $$$K$$$-th nearest special vertex to it.

For $$$K=1$$$, I realize that this is just a BFS, starting from special vertex can get $$$\mathcal{O}(V+E)$$$ complexity.

But when $$$K>1$$$, I have no idea how to optimize the BFS that can get better complexity that brute force $$$\mathcal{O}(V(V+E))$$$

I am wondering is there any algorithm to find out the answer more efficiency, such as $$$\mathcal{O}(K(V+E))$$$ or $$$\mathcal{O}(V+E)$$$.


Read more »

  • Vote: I like it
  • +7
  • Vote: I do not like it