All-pairs shortest paths with a sublinear additive error
All-pairs shortest paths with a sublinear additive error
复制标题
具有次线性加性误差的全对最短路径
DOI：
10.1145/2000807.2000813
复制
发表时间：
2008
影响因子：
0.5
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
L. Roditty;A. Shapira
我们表明，对于每0≤p</i>≤1，都有一个<i> o </i>（<i> n </i> <sup> 2.575- <i> p </ i> i>/（7.4-2.3 <i> p </i>）</sup>） - 给定有针对较小整数的有向图的时间算法，估计每对顶点之间最短路径的长度< i> u </i>，<i> v </i>在图中，在附加错误Δ<sup>> <i> p </i> </sup>（<i> u </i>， <i> v </i>），在哪里δ（<i> u </i>，<i> v </i>）是<i> u </i>和<i> v </i>之间的最短路径的确切长度对于任何0 <i> p </i>≤1，用于计算确切最短路径的最快算法的速度要快。
以前，“击败”确切最短路径算法的运行时间的唯一方法是应用Zwick [2002]的算法，该算法近似于（1 +ε）的乘法误差中的最短路径距离。最快的最短路径算法与最快的近似算法之间的定性和定量过渡，实际上是线性添加误差。我们需要获得上述结果，这本身也很有趣，是用于最短路径的计算算法（1 +ε）乘法近似值，其运行时间比Zwick近似算法的运行时间快于Zwick的运行时间。 ε<1，该图具有较小的整数重量。
We show that, for every 0 ≤ <i>p</i> ≤ 1, there is an <i>O</i>(<i>n</i><sup>2.575−<i>p</i>/(7.4−2.3<i>p</i>)</sup>)-time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path between every pair of vertices <i>u</i>, <i>v</i> in the graph to within an additive error Δ<sup><i>p</i></sup>(<i>u</i>, <i>v</i>), where Δ(<i>u</i>, <i>v</i>) is the exact length of the shortest path between <i>u</i> and <i>v</i>. This algorithm runs faster than the fastest algorithm for computing exact shortest paths for any 0 < <i>p</i> ≤ 1.
Previously the only way to “beat” the running time of the exact shortest path algorithms was by applying an algorithm of Zwick [2002] that approximates the shortest path distances within a multiplicative error of (1 + ε). Our algorithm thus gives a smooth qualitative and quantitative transition between the fastest <i>exact</i> shortest paths algorithm, and the fastest approximation algorithm with a linear additive error. In fact, the main ingredient we need in order to obtain the above result, which is also interesting in its own right, is an algorithm for computing (1 + ε) multiplicative approximations for the shortest paths, whose running time is faster than the running time of Zwick's approximation algorithm when ε ≪ 1 and the graph has small integer weights.