Before revision:  We also devise efficient algorithms for computing (\le \le 1 +\epsilon)-approximate shortest paths from each vertex to its k nearest neighbors in directed graphs.
After revision:  We also devise efficient algorithms for computing (\le \le 1 +\epsilon)-approximate shortest paths from each vertex to its k nearest neighbors in graphs.