Gupta, ManojManojGupta2025-09-042026-04-022025-09-042025-12-1410.1109/FOCS63196.2025.000652-s2.0-105034376113https://repository.iitgn.ac.in/handle/IITG2025/30750An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in O~(n2+O(1k)) time1, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least k apart, where k ≥ 2. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same O~(n2+1k) runtime but applies to vertex pairs merely O(log k) apart, where logk≥1. When k=log n, the running time of our algorithm is O~(n2) and it works for all pairs at least O(loglogn) apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.en-USConference Paper123456789/433