Let $G=(V,E,w)$ be a weighted undirected graph with $n$ vertices and $m$ edges, and fix a set of $s$ sources $S\subseteq V$. We study the problem of computing { \em almost shortest paths} (ASP) for all pairs in $S \times V$ in both classical centralized and parallel (PRAM) models of computation. Consider the regime of multiplicative approximation of $1+\epsilon$, for an arbitrarily small constant $\epsilon > 0$ . In this regime existing centralized algorithms require $\Omega(\min\{ |E|s,n^\omega\})$ time, where $\omega < 2.372$ is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work $\Omega(\min\{ |E|s,n^\omega\})$. Our centralized algorithm has running time $O((m+ ns)n^\rho)$, and its PRAM counterpart has polylogarithmic depth and work $O((m + ns)n^\rho)$, for an arbitrarily small constant $\rho > 0$. For a pair $(s,v) \in S\times V$, it provides a path of length $\hat{ d}(s,v)$ that satisfies $\hat{ d}(s,v) \le (1+\epsilon)d_G(s,v) + \beta \cdot W(s,v)$, where $W(s,v)$ is the weight of the heaviest edge on some shortest $s-v$ path. Hence our additive term depends linearly on a { \em local} maximum edge weight, as opposed to the global maximum edge weight in previous works. Finally, our $\beta = (1/\rho)^{ O(1/\rho)}$. We also extend a centralized algorithm of Dor et al. \cite{ DHZ00}. For a parameter $\kappa = 1,2,\ldots$, this algorithm provides for { \em unweighted} graphs a purely additive approximation of $2(\kappa -1)$ for { \em all pairs shortest paths} (APASP) in time $\tilde{ O}(n^{ 2+1/\kappa})$. Within the same running time, our algorithm for { \em weighted} graphs provides a purely additive error of $2(\kappa - 1) W(u,v)$, for every vertex pair $(u,v) \in { V \choose 2}$, with $W(u,v)$ defined as above. On the way to these results we devise a suit of novel constructions of spanners, emulators and hopsets.
Categories: cs.DS