A computer scientist breaks through a limit that stood since 1996

That challenge extends far beyond maps. Similar calculations are important for transportation systems, communication networks, and even biological structures involving proteins, neurons, or other interconnected components. As these networks grow, determining the shortest routes between all their points becomes increasingly difficult.

Computer scientists call this the All-Pairs Shortest Paths (APSP) problem. It involves finding the shortest distance between every pair of points in a graph. In this context, a 'graph' is simply a collection of points (called vertices) joined by connections (called edges). Those points might represent cities, PCs, subway stations, or organs, while the connections could stand for highways, cables, railway lines, or blood vessels.

Why Calculating Shortest Paths Is So Difficult

Determining the exact shortest distances across a massive network can consume enormous amounts of computing time and memory. In densely connected networks, some conventional approaches require what mathematicians call cubic time. That means doubling the number of points can increase the computational workload by roughly eight times.

Because the required computation (work) can grow much faster than the network itself, researchers have spent decades searching for more efficient methods. One promising solution is to use approximation algorithms, which calculate estimates rather than exact answers. The goal is to produce distances that are sufficiently accurate while dramatically reducing the amount of computation required.

An important advance came in 1996, when researchers Dor, Halperin, and Zwick (DHZ) developed a method capable of producing distance estimates within twice the actual shortest distance for sufficiently distant points, while operating in nearly optimal time.

This level of accuracy is known as a "2‑approximation." For example, if the shortest possible route between two locations is 10 kilometers, an estimate satisfying this guarantee would fall between 10 and 20 kilometers.

Rather than examining every possible route, the DHZ approach uses a relatively small selection of points from the network (referred to as sampled vertices). These strategically selected points serve as shortcuts that help the algorithm estimate distances more efficiently.

A Clever Shortcut With a Hidden Weakness

The approach works particularly well when the points being compared are far apart.

Consider a journey between Delhi and Chennai. Because the cities are separated by a considerable distance, the algorithm can often find a sampled point close to the shortest route. This allows it to calculate an estimate that remains within the promised limit of twice the actual distance.

However, the same strategy becomes less dependable when the two points are close together.

Imagine calculating the shortest route between two neighborhoods in the Mumbai suburbs. The sampled points might be located too far from the most direct connection, forcing the algorithm to estimate a much longer route.

For example, two points might be connected by a path containing just two edges, yet the sampled route could contain five. Because five exceeds twice the true distance of two, the result violates the "at most twice" accuracy guarantee.

This weakness meant that the original algorithm's mathematical guarantee applied only when the points were sufficiently far apart. For closer connections, the same level of accuracy could not always be assured.

That limitation remained a challenge for nearly three decades.

A New Algorithm Breaks Through a Decades-Old Limit

Now, Dr. Manoj Gupta, an Associate Professor at the Indian Institute of Technology Gandhinagar, has introduced a refinement that extends the accuracy guarantee to points much closer together than earlier methods allowed.

Gupta presented his 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 achievement is particularly significant because the improved algorithm preserves the overall runtime of the earlier approach while expanding the range of distances for which reliable estimates can be guaranteed.

The breakthrough comes from rethinking how points are sampled within the network.

Traditional methods depended on a collection of representative points to estimate distances. Gupta's approach instead introduces a multi-scale sampling strategy that organizes information about the network at several different levels.

By analyzing connections at multiple scales rather than relying on a single sampling layer, the algorithm can account for shorter routes that previous approaches might overlook.

This more sophisticated sampling technique reduces the minimum distance required for the 2-approximation guarantee to hold, without increasing the algorithm's overall computational complexity.

Returning to the transportation example, the original DHZ method could efficiently estimate sufficiently long journeys, such as the route between Delhi and Chennai. The improved approach extends that dependable accuracy to much shorter connections (such as Mumbai's suburbs).

The central achievement is not simply a new way to estimate distances. It is the ability to provide the same mathematical accuracy guarantee across a wider range of distances while maintaining computational efficiency.

Why This Computer Science Breakthrough Matters

Massive networks are fundamental to modern technology. Internet infrastructure, transportation systems, social media platforms, and artificial intelligence applications all depend on analyzing complicated webs of interconnected information.

In many situations, obtaining a perfectly exact distance is less important than producing a dependable estimate quickly. When networks contain enormous numbers of connections, the ability to balance accuracy and speed becomes especially valuable.

Gupta's research strengthens the mathematical foundations of algorithms designed to handle these challenges. Although the findings are theoretical and do not establish immediate improvements to specific commercial systems, they offer a better way to approach distance calculations in large networks.

The work also provides insight into how the overall structure of a network can be understood through carefully selected local connections. By improving how these relationships are sampled and analyzed, researchers can move closer to efficiently estimating distances between every pair of points in a massive system.

Progress in theoretical computer science often comes through incremental refinements rather than dramatic changes. Improving an influential result that dates back to 1996 therefore represents a meaningful advance.

By extending a longstanding accuracy guarantee without increasing overall runtime, the new algorithm pushes beyond an important mathematical boundary and strengthens the techniques underlying some of today's most complex connected systems.