### practice080's blog

By practice080, 6 weeks ago,

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

Thanks!