A computer scientist breaks through a limit that stood since 1996

The all-pairs shortest-path problem asks computers to estimate or calculate the distance between every pair of points in a network, such as cities linked by roads or devices linked by cables. Exact calculations can become prohibitively expensive as networks grow, so researchers use faster approximation algorithms. A landmark 1996 method, developed by Dor, Halperin, and Zwick, offered nearly optimal running time and a guarantee that estimated distances would be no more than twice the true distance - but only for pairs that were sufficiently far apart. For nearby points, its sampled shortcuts could miss short routes and produce estimates that exceeded that accuracy limit.

Manoj Gupta of the Indian Institute of Technology Gandhinagar has developed a refinement that extends the same two-times accuracy guarantee to closer pairs without increasing the earlier method’s overall computational complexity. Presented at the 2025 Foundations of Computer Science symposium, the work uses a multi-scale sampling strategy: instead of relying on one layer of representative network points, it examines connections at several scales, helping capture short routes that could otherwise be overlooked. The result is a broader range of reliable estimates while retaining the method’s speed. The advance is theoretical rather than an immediate upgrade to a particular navigation or commercial system, but it strengthens tools for analyzing large transportation, communications, biological, and other networks where quick, dependable distance estimates matter.