Let G = (V,E) be a weighted undirected graph with n vertices and m edges, and let d_G(u,v) be the length of the shortest path between u and v in G. In this paper we present a unified approach for obtaining algorithms for all pairs approximate shortest paths in weighted undirected graphs. For every integer k ≥ 2 we show that there is an Õ(n²+kn^{2-3/k}m^{2/k}) expected running time algorithm that computes a matrix M such that for every u,v ∈ V: d_G(u,v) ≤ M[u,v] ≤ (2+(k-2)/k)d_G(u,v). Previous algorithms obtained only specific approximation factors. Baswana and Kavitha [FOCS 2006, SICOMP 2010] presented a 2-approximation algorithm with expected running time of Õ(n²+m√ n) and a 7/3-approximation algorithm with expected running time of Õ(n²+m^{2/3}n). Their results improved upon the results of Cohen and Zwick [SODA 1997, JoA 2001] for graphs with m = o(n²). Kavitha [FSTTCS 2007, Algorithmica 2012] presented a 5/2-approximation algorithm with expected running time of Õ(n^{9/4}). For k = 2 and k = 3 our result gives the algorithms of Baswana and Kavitha. For k = 4, we get a 5/2-approximation algorithm with Õ(n^{5/4}m^{1/2}) expected running time. This improves upon the running time of Õ(n^{9/4}) due to Kavitha, when m = o(n²). Our unified approach reveals that all previous algorithms are a part of a family of algorithms that exhibit a smooth tradeoff between approximation of 2 and 3, and are not sporadic unrelated results. Moreover, our new algorithm uses, among other ideas, the celebrated approximate distance oracles of Thorup and Zwick [STOC 2001, JACM 2005] in a non standard way, which we believe is of independent interest, due to their extensive usage in a variety of applications.

Let G = (V, E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an Õ(n2)-time algorithm that computes estimated distances with a multiplicative approximation of 3. Berman and Kasiviswanathan [WADS 2007] improved the approximation of Dor et al. and presented an Õ(n2)-time algorithm that produces for every u, v ϵ V an estimate (u, v) such that: dG(u, v) ≤ (u, v) ≤ 2dG(u, v) + 1. We refer to such an approximation as an (α, β)-approximation, where a is the multiplicative approximation and β is the additive approximation. A prerequisite for an O(n2−ε)-time algorithm, where ε ϵ (0, 1), is a data structure that uses O(n2−δ) space, for some δ ≥ ε, and answers queries in constant time. An O(n2−ε)-time (3, 0)-approximation algorithm became plausible after Thorup and Zwick [STOC 2001, JACM 2005] presented their approximate distance oracles, and in particular an O(n1.5)-space data structure that reports a (3, 0)-approximate distance in O(1) time. Indeed, using Thorup and Zwick distance oracles together with more ideas, Baswana, Gaur, Sen, and Upadhyay [ICALP 2008] improved the running time of Dor et al., and obtained an O(n2−ε) time algorithm, at the cost of introducing also an additive approximation. They presented an algorithm that in Õ(m + n23/12) expected running time constructs an O(n1.5)-space data structure, that in O(1) time reports a (3, 14)-approximate distance. An O(n2−ε)-time (2, 1)-approximation algorithm became plausible only after Pǎtraşcu and Roditty [FOCS 2010, SICOMP 2014] presented an O(n5/3)-space data structure that reports (2, 1)-approximate distances in O(1) time. However, only few years ago, Sommer [ICALP 2016] obtained an Õ(n2) time algorithm that computes a (2, 1)-distance oracle with Õ(n5/3) space. This leads to the following natural question of whether Ω(n2) time is a lower bound for any (3−α, β)-approximation, where α ϵ (0, 1), and β is constant. In this paper we show that this is not the case by presenting an algorithm that for every ε ϵ (0, 1/2) computes in Õ(m) + n2−Ω(ε) time an -space data structure that in O(1/ε) time reports, for every u, v ϵ V, an estimate (u, v) such that: Our result improves, simultaneously, the running time and the multiplicative approximation of the Õ(n2)-time (3, 0)-approximation algorithm of Dor et al. at the cost of introducing also an additive approximation.