Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

We present a +2₈=₁^k+1Wᵢ-APASP algorithm for dense weighted graphs with runtime O (n^2+1{3k+2}), where W₈ is the weight of an iᵗh heaviest edge on a shortest path. Dor, Halperin and Zwick FOCS'96, SICOMP'00 had two algorithms for the commensurate unweighted +2 (k+1) -APASP: O (n^2-1{k+2}m^1{k+2}) runtime for sparse graphs and O (n^2+1{3k+2}) runtime for dense graphs. Cohen and Zwick SODA'97, JALG'01 adapted the sparse variant to weighted graphs: +2₈=₁^k+1Wᵢ-APASP algorithm in the same runtime. We show an algorithm for dense weighted graphs. For nearly additive APASP, we present a (1+, \2W₁, 4W₂\) -APASP algorithm with O ( (1) ^O (1) n^2. 15135313 W) runtime. This improves the (1+, 2W₁) -APASP of Saha and Ye SODA'24. For multiplicative APASP, we show a framework of (3 +4 + 2+) -APASP algorithms, reducing the runtime of Akav and Roditty ESA'21 for dense graphs and generalizing the (2+) -APASP algorithm of Dory et al SODA'24. Our base case is a (73+) -APASP in O ( (1) ^O (1) n^2. 15135313 W) runtime, improving the 73-APASP algorithm of Baswana and Kavitha FOCS'06, SICOMP'10 for dense graphs. Finally, we "bypass" an Ω (n^ω) conditional lower bound by Dor, Halperin, and Zwick for α-APASP with α< 2, by allowing an additive term (e. g. 6k+3{3k+2, ₈=₁^k+1W₈}-APASP in O (n^2+1{3k+2}) runtime. ).