A computer scientist has improved a classic algorithm used to estimate shortest paths across large networks, extending a mathematical guarantee that had remained largely unchanged since 1996.
The advance focuses on the All-Pairs Shortest Paths (APSP) problem, one of the fundamental challenges in graph algorithms.
APSP asks a seemingly simple question: if a network contains many interconnected points, what is the shortest distance between every possible pair?
In small networks, this can be calculated exactly.
But as networks grow, the computational cost increases rapidly.
A new algorithm developed by Manoj Gupta, associate professor at the Indian Institute of Technology Gandhinagar, uses a multiscale sampling strategy to improve distance estimates for vertex pairs that are relatively close together.
The work was presented at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025).
Why Shortest Paths Matter
Graphs are mathematical structures used to represent connected systems.
The individual points in a graph are known as vertices, while the connections between them are called edges.
Many real-world systems can be represented this way.
Vertices might represent cities, computers, railway stations, proteins, neurons or social-media users.
Edges could represent roads, communication links, railway lines, biological interactions or social connections.
Finding the shortest path between two vertices is therefore useful in many fields.
Navigation systems, network routing, transportation planning, artificial intelligence and biological analysis can all depend on efficient path calculations.
The Challenge of Calculating Every Pair
Finding the shortest route between one pair of vertices is already a familiar computational problem.
APSP goes much further.
For a graph containing n vertices, researchers may need to determine distances for roughly n² pairs.
That alone creates a large amount of output.
The computation can be even more demanding.
For dense graphs, conventional exact algorithms can require approximately cubic running time.
That means that if the number of vertices doubles, the amount of work can increase by roughly a factor of eight.
For extremely large networks, exact solutions can therefore become impractical.
Why Approximation Algorithms Are Useful
To reduce this computational burden, computer scientists often use approximation algorithms.
These algorithms sacrifice some precision in exchange for much greater speed.
Instead of finding the exact shortest path, an approximation algorithm produces an estimate while guaranteeing that the estimate will remain within a defined range of the true answer.
This can be extremely useful in large systems where an approximate answer is sufficient.
If a network contains millions of vertices, obtaining a fast and mathematically reliable estimate can be more practical than waiting for an exact result.
The Influential 1996 Algorithm
In 1996, researchers Dor, Halperin and Zwick developed an influential algorithm for approximate all-pairs shortest paths.
Often referred to as the DHZ algorithm, it achieved a 2-approximation while operating in nearly optimal time.
A 2-approximation means that the estimated distance between two vertices will not be more than twice the actual shortest-path distance, within the range where the guarantee applies.
For example, if the true distance is 10 units, the algorithm could report a value between 10 and 20.
This represented an important balance between speed and accuracy.
Using Sampled Vertices as Landmarks
The DHZ algorithm avoids examining every possible route in full.
Instead, it selects a relatively small number of vertices to serve as sampled landmarks.
Distances between other vertices can then be estimated partly by using these landmark points.
This strategy works particularly well when two vertices are far apart.
A long shortest path contains many vertices, increasing the chance that one of the sampled landmarks will lie on or near the route.
Using that landmark may only introduce a relatively small detour.
As a result, the estimated distance remains within the promised approximation factor.
The Problem With Nearby Vertices
The challenge becomes more serious when two vertices are close together.
A short path may contain only a few edges.
Because the route contains so few vertices, there is a lower chance that one of the sampled landmarks lies nearby.
The algorithm may therefore have to estimate the distance by routing through a much more distant sampled vertex.
That detour can become disproportionately large compared with the true distance.
For example, if the actual shortest path between two vertices contains only two edges, an indirect estimate involving five edges would exceed the desired factor-of-two guarantee.
This created a longstanding blind spot.
A Limitation That Persisted for Decades
The original algorithm was highly effective for sufficiently distant vertex pairs.
But extending its guarantee to much closer pairs proved difficult.
For almost three decades, improving this threshold while preserving the algorithm's efficiency remained a challenging theoretical problem.
Gupta's work addresses this limitation.
Instead of relying on a single set of sampled landmarks, the new method organizes sampled vertices across multiple scales.
Sampling the Network at Several Levels
The core idea is multiscale sampling.
Different groups of vertices are sampled at different densities or structural scales.
Each level captures a different portion of the graph's distance structure.
This makes it more likely that even relatively short paths will have a useful sampled vertex nearby.
The algorithm can therefore choose an appropriate reference point depending on the distance between the vertex pair being evaluated.
This gives the method more flexibility than a single-scale sampling strategy.
Why Multiple Scales Help
Imagine trying to estimate distances using landmarks placed across a large country.
Large cities might be useful when estimating a journey between opposite sides of the country.
But those same landmarks might be poor choices for estimating the distance between two nearby streets.
A multiscale system would include landmarks at national, regional and local levels.
The algorithm could then choose the scale best suited to the distance being measured.
Gupta's approach applies a similar idea mathematically to graphs.
Extending the 2-Approximation Guarantee
The new algorithm does not reduce the approximation factor below two.
Its estimates can still be as large as twice the true shortest-path distance.
Instead, the key improvement is that this guarantee now applies to closer vertex pairs than before.
In other words, the region where the approximation guarantee can be trusted becomes larger.
The algorithm achieves this improvement while retaining at least the same overall time complexity.
That balance is important because an algorithm that improves accuracy but becomes dramatically slower may offer little practical advantage for enormous graphs.
Why Short Distances Are Mathematically Difficult
Long paths naturally provide more opportunities for sampling.
If a shortest path contains many vertices, even a relatively sparse sample is likely to intersect or approach that route.
Short paths are different.
A path containing only a few edges offers fewer opportunities for a sampled vertex to appear nearby.
This makes it harder to estimate its distance accurately using landmark-based methods.
The multiscale approach addresses this by creating denser or differently structured samples at several levels.
The Result Is Mainly Theoretical
The research is a theoretical advance in algorithm design.
It does not immediately replace navigation systems such as Google Maps or other commercial routing software.
Real-world routing applications involve many additional factors, including road restrictions, traffic conditions, changing travel times and geographic constraints.
However, theoretical advances often shape future practical algorithms.
Improved mathematical guarantees reveal new ways of organizing computation and can eventually influence systems that work with extremely large networks.
Applications Across Connected Systems
Shortest-path algorithms are useful far beyond road navigation.
In computer networks, they can help determine efficient paths for transmitting information.
In transportation systems, they can assist with route planning.
In social networks, graph distances can describe relationships between users.
In biology, graphs can represent interactions among proteins, genes or neurons.
Artificial intelligence systems also increasingly use graph-based representations for connected data.
For such enormous networks, exact shortest-path calculations may be unnecessarily expensive.
Approximation algorithms with strong guarantees can provide a better balance between speed and reliability.
Why Mathematical Guarantees Matter
An approximation algorithm is most useful when researchers know precisely how inaccurate its answer can become.
Without such a guarantee, a fast answer might sometimes be excellent and sometimes extremely misleading.
A 2-approximation gives a clear upper bound.
The algorithm may not return the exact shortest path, but its estimate cannot exceed twice the true distance within the cases covered by the theorem.
Extending that guarantee to more vertex pairs therefore makes the algorithm more broadly reliable.
Small Improvements Can Be Important in Theory
Advances in theoretical computer science often involve improving limits that may initially appear modest.
A small improvement to an approximation bound or running-time threshold can represent years of mathematical work.
Such results matter because they reveal what is computationally possible.
In this case, the important achievement is not simply that a new algorithm is faster.
It is that a long-standing boundary on where a classic approximation guarantee could be applied has been pushed further.
Revisiting a 1996 Idea With a New Strategy
The result demonstrates how older algorithms can continue to inspire new research decades later.
The original DHZ algorithm introduced an efficient way to approximate all-pairs shortest paths using sampled vertices.
Gupta's multiscale strategy builds on that idea rather than discarding it.
By sampling the graph at several levels, the new algorithm overcomes part of the weakness that appeared when vertex pairs were too close together.
The approach therefore extends a foundational idea using a more refined understanding of graph structure.
Toward Faster Analysis of Massive Networks
As datasets and networks continue to grow, efficient graph algorithms will become increasingly important.
Networks containing millions or billions of connections appear throughout science, engineering and technology.
Calculating every possible shortest path exactly may be impossible or unnecessary in many such systems.
Approximation algorithms provide another option.
By improving how reliably they handle both distant and nearby vertices, researchers can extract useful structural information without paying the full computational cost of exact calculations.
The new work represents another step toward that goal.
Nearly 30 years after the original algorithm established its influential guarantee, multiscale sampling has pushed that guarantee into territory that had remained difficult to reach.
Journal reference
Manoj Gupta. “Improved 2-Approximate Shortest Paths for Close Vertex Pairs.” 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), 14–17 December 2025.