A new algorithm solves a blind spot that has challenged computer scientists since 1996, improving distance estimates for nearby points in massive networks.
Navigation apps usually solve one route at a time, such as finding the fastest way from a hotel to an airport. Computer scientists face a far larger version of that challenge: calculating the shortest distance between every possible pair of locations in a network.
Known as the All-Pairs Shortest Paths (APSP) problem, this task applies to far more than road maps. A graph can represent computers connected by data links, stations joined by rail lines, proteins interacting inside a cell, or neurons communicating in the brain. The points are called vertices, and the connections between them are edges.
Why Massive Networks Overwhelm Computers
Exact calculations become expensive as a network grows. For dense graphs, conventional methods can require cubic time. Doubling the number of vertices may therefore produce roughly eight times as much work. The output itself is also enormous because a network with n vertices contains n² ordered pairs whose distances may need to be reported.
That scaling problem has driven the search for approximation algorithms. These methods trade a limited amount of precision for major gains in speed, producing answers that are not exact but remain within a mathematically defined range.
In 1996, Dor, Halperin, and Zwick introduced an influential method that delivered a “2-approximation” in nearly optimal time. Its estimate would not exceed twice the true shortest distance. If two locations were actually 10 kilometers (6.2 miles) apart, for example, the reported distance would fall between 10 and 20 kilometers (6.2 and 12.4 miles).
A Fast Shortcut With a Blind Spot
The DHZ algorithm avoids examining every route in full. Instead, it selects a relatively small collection of representative points, known as sampled vertices, and uses them as landmarks for estimating distances elsewhere in the network.
This strategy performs well when two vertices are far apart. On a route comparable to a journey between New York City and Los Angeles, there is a good chance that at least one sampled vertex lies near the shortest path. Passing through that landmark may add only a modest detour, keeping the estimate within the promised factor of two.
Short routes are more difficult. Two neighborhoods in the Los Angeles suburbs, for instance, might be connected by a path containing only two edges, yet neither may sit near a sampled vertex. Traveling through a distant landmark could produce an estimate of five edges, which is more than twice the true distance.
The algorithm was therefore fast and dependable for sufficiently distant pairs, but its guarantee did not extend as effectively to nearby vertices. That boundary resisted improvement for almost 25 years.
Sampling the Graph at Multiple Scales
Manoj Gupta, an associate professor at the Indian Institute of Technology Gandhinagar, presented a new solution at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025).
Rather than depending on one layer of sampled vertices, Gupta’s algorithm arranges samples across several scales. Each layer captures a different level of the graph’s structure, increasing the likelihood that an appropriate reference point will be available even when the shortest path is relatively brief.
This multiscale design lowers the distance threshold at which the 2-approximation guarantee applies. In practical terms, the algorithm can provide dependable estimates for much closer vertex pairs than earlier approaches while retaining at least the same overall time complexity.
The estimate is still allowed to reach twice the true distance. Instead, the improvement greatly expands the range of pairs for which that promise can be made, bringing nearby points within reach without sacrificing speed.
Stronger Foundations for Connected Systems
Large graphs underpin internet routing, transportation planning, social platforms, biological research, and artificial intelligence systems that process relationships between connected data. Exact distances are not always necessary in such settings. A rapid estimate with a firm accuracy guarantee may be far more useful than a perfect answer that takes too long to calculate.
The result remains a theoretical advance rather than a ready-made replacement for commercial navigation software. Even so, stronger theoretical bounds can shape future algorithms by revealing more efficient ways to extract reliable information from networks containing vast numbers of connections.
Progress in graph theory often comes through small improvements to long-established limits. Extending a guarantee that had largely stood since 1996 represents a meaningful step toward fast, scalable distance calculations across the immense networks woven into modern technology and science.
Reference: “Improved 2-Approximate Shortest Paths for close vertex pairs” by Manoj Gupta, 14-17 December 2025, 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS).
DOI: 10.1109/FOCS63196.2025.00065
Never miss a breakthrough: Join the SciTechDaily newsletter.
Follow us on Google and Google News.