Distance from a set of vertices in directed graph

I'm designing an algorithm for finding the minimum distance of a given vertex v from a subset of vertices A(that is from an element of this subset). I need to find the value k such that:

• distance from x to v is k, for some x in A
• distance from y to v is >=k, for all y in A.

My solution consist in开发者_开发知识库:

• getting the transpose graph G'
• visiting G' starting from v, using BFS.
• find the minimum distance from the vertices in A

And I think this works and it should run in O(|V|+|E|) time. My question is: there is a better solution to this problem?

---

No, there isn't better solution.
Consider the following: 1-2-3-4,A={4}, v=1. you will have to iterate all V,E in the graph [you must read all the path], making this problem Omega(V+E). since your algorithm is correct [simple to prove], and is O(V+E) [triviialy, creating G' and BFS], and the problem is Omega(V+E), your solution is optimal, in terms of big O notation.

---

There's no hope for improving the asymptotic worst case, but a practical optimization is search simultaneously from A and v until the searches meet (always choose to update the smaller frontier).