Approximate shortest paths in weighted graphs

摘要

We present an approximation algorithm for the all pairs shortest paths (APSP) problem in weighed graphs. Our algorithm solves the APSP problem for weighted directed graphs, with real (positive or negative) weights, up to an additive error of ϵ. For any pair of vertices u,v, the algorithm finds a path whose length is at most δ(u,v)+ϵ. The algorithm is randomized and runs in O˜(n(ω+3)/2)