Given a weighted undirected graph with $m = o(n^2)$ edges, I would like to compute distances of approximation less than 2 between any given pair of vertices. Of course, I would like to use subquadratic space and sublinear query time. I am aware of Zwick's result that uses matrix multiplication, but I am curious if any combinatorial algorithms are known for this problem?
Computing distances with approximation less than 2 in general graphs?
ds.algorithms;graph algorithms