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

We present a +2∑ᵢ₌₁ᵏ⁺¹Wᵢ-APASP algorithm for dense weighted graphs with runtime O(n2+1/3k+2), where Wᵢ is the weight of an iᵗʰ 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(n2-1/k+2m1/k+2) runtime for sparse graphs and O(n2+1/3k+2) runtime for dense graphs. Cohen and Zwick [SODA'97, JALG'01] adapted the sparse variant to weighted graphs: +2∑ᵢ₌₁ᵏ⁺¹Wᵢ-APASP algorithm in the same runtime. We show an algorithm for dense weighted graphs. For nearly additive APASP, we present a (1+ε,min\2W₁,4W₂\)-APASP algorithm with O((1/ε)O(1)· n2.15135313·log 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 (7/3+ε)-APASP in O((1/ε)O(1)· n2.15135313· log W) runtime, improving the 7/3-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,∑ᵢ₌₁ᵏ⁺¹Wᵢ-APASP in O(n2+1/3k+2) runtime.).