Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Michael Elkin, Yuval Gitlitz, Ofer Neiman

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…