Search Results

We present a +2∑_{i=1}^{k+1} W_i-APASP algorithm for dense weighted graphs with a runtime of Õ(n^{2+1/(3k+2)), where W_i is the weight of an i^th heaviest edge on a shortest path between two vertices. Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] introduced two algorithms for the commensurate unweighted +2⋅ (k+1)-APASP problem: one for sparse graphs with a runtime of Õ(n^{2-1/(k+2)} m^{1/(k+2)}) and one for dense graphs with a runtime of Õ(n^{2+1/(3k+2)}). Subsequently, Cohen and Zwick [SODA'97 and JALG'01] adapted the algorithm for sparse graphs to the weighted setting, namely a +2∑_{i=1}^{k+1} W_i-APASP algorithm with the same Õ(n^{2-1/(k+2)} m^{1/(k+2)}) runtime. We fill the nearly three decades old gap by providing an algorithm for dense weighted graphs, matching the runtime for the unweighted setting. In addition, we explore nearly additive APASP, where the multiplicative stretch is 1+ε. We present a (1+ε, min{2W₁,4W₂})-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves upon Saha and Ye [SODA'24], which had the same runtime, yet (1+ε, 2W₁)-APASP. For pure multiplicative APASP, we present a (7/3+ε)-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves, for dense graphs, the Õ(nm^{2/3}+n²) runtime of the 7/3-APASP algorithm by Baswana and Kavitha [FOCS'06 and SICOMP'10], at the cost of introducing an additional ε to the multiplicative stretch. We further view this result in a broader framework of ((3𝓁+4)/(𝓁+2) + ε)-APASP algorithms, similarly to the family of (3𝓁+4)/(𝓁+2)-APASP algorithms by Akav and Roditty [ESA'21]. This also generalizes the (2+ε)-APASP algorithm by Dory, Forster, Kirkpatrick, Nazari, Vassilevska Williams, and de Vos [SODA'24]. Finally, we show that it is possible to "bypass" an Ω̃ (n^ω) conditional lower bound by Dor, Halperin, and Zwick for α-APASP with α < 2, by allowing an additive component to the approximation (e.g. a ((6k+3)/(3k+2),∑_{i=1}^{k+1} W_i)-APASP with Õ(n^{2+1/(3k+2)}) runtime.).