A computer scientist breaks through a limit that stood since 1996

Dr. Manoj Gupta, an Associate Professor at the Indian Institute of Technology Gandhinagar, has improved an algorithm for finding shortest paths in large networks. The breakthrough refines a method developed in 1996 by researchers Dor, Halperin, and Zwick (DHZ).

The All-Pairs Shortest Paths (APSP) problem asks: what is the shortest distance between every pair of points in a graph? Navigation apps solve simpler versions daily, but calculating this for massive networks with all point pairs becomes computationally expensive. In densely connected networks, conventional approaches require cubic time, meaning doubling the number of points multiplies the workload by roughly eight times.

The DHZ method produced distance estimates within twice the actual shortest distance for sufficiently distant points while operating in nearly optimal time. This "2-approximation" guarantee works well for faraway locations. For example, estimating a route between distant Delhi and Chennai, the algorithm could often find a sampled point near the shortest route.

The original method failed for closer connections. Two nearby points might be separated by two edges, yet the sampled route could contain five, violating the "at most twice" accuracy guarantee.

Gupta's refinement extends this accuracy guarantee to much closer point pairs without increasing overall computational complexity. He replaced single-layer sampling with a multi-scale sampling strategy that organizes network information at several different levels. This approach accounts for shorter routes that previous methods overlooked.

Gupta presented the research at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025) in a paper titled "Improved 2-Approximate Shortest Paths for close vertex pairs." The findings are theoretical rather than immediately applicable to commercial systems, but they strengthen the mathematical foundations underlying distance calculations in large networks used by Internet infrastructure, transportation systems, and artificial intelligence applications.