# Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $$v$$ than node $$w$$ ($$dist(x,v) < dist(x,w)$$). The solution that comes to my mind is running two BFS, which gives us $$\mathcal{O}(V + E)$$ running time.

Is there any better way to do this? possibly with one BFS?

EDIT: We can start two BFS from $$w$$ and $$v$$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $$w$$ then the nodes in distance 1 of $$v$$ and then nodes at distance 2 of $$w$$ and so on. by the time there is no node in the queue of BFS of node $$v$$, we can end the search. any node which is first visited with $$v$$ BFS is closer to $$v$$ than $$w$$.

But again I suppose there is a more efficient way to do this.

• Please clarify that whether "any node which is closer to node $v$ than node $w$" means "any node $x$ such that $dist(x,v)<dist(w,v)$ " or "any node $x$ such that $dist(x,v)<dist(x,w)$". – Apass.Jack May 23 at 2:49
• I edited the post. – mahdi gh May 23 at 9:04

I will assume that you have as input a graph $$G = (V, E)$$. Let $$dist$$ be a vector which stores the distance of all nodes of your graph to node $$v \in V$$.
You must run a BFS algorithm starting on node $$v$$ and store the distance from each node to $$v$$ in $$dist$$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $$i$$ such that $$dist[i]$$ < $$dist[w]$$.
The overall complexity of this algorithm is $$\mathcal{O}(V + E + V)$$. In a tree, we have that $$|E| = |V|-1$$. Thus, the complexity is $$\mathcal{O}(3 V) = \mathcal{O}(V)$$.
• I am afraid this answer is wrong. Consider the graph with edges $xu$, $uv$ and $vw$. $dist_v[x]=2 > dist_v[w]=1$. However, $x$ is nearer to $v$ than $w$. – Apass.Jack May 23 at 0:30
• Why $x$ is nearer to $v$ than $w$? In your example, $dist_v[w] = 1$ (it follows the path $<w, v>$) and $dist_v[x] = 2$ (it follows the path $<x, u, v>$). Thus, you will not delete or mark node $x$. – Iago Carvalho May 23 at 1:21
• I see now... There are two possible interpretations of this question. The first one (which I answered) is to find the nodes whose distance to $v$ are smaller than the distance from $v$ to $w$. The second interpretation (which I now answered) is @Appas Jack interpretation. – Iago Carvalho May 23 at 1:28