TECH

Shortest paths research narrows a 25-year gap in graph algorithms

Most of you have used a navigation app like Google Maps for your travels at some point. These apps rely on algorithms that compute shortest paths through vast networks. Now imagine scaling that task to calculate distances between every pair of points in a massive system, for example, a transportation grid, a communication backbone, or even a biological network such as protein or neural interaction networks.

This is the classic "all-pairs shortest paths" (APSP) problem, one of the central challenges in theoretical computer science. In short, APSP asks for the shortest-path distance between every pair of vertices in the graph. Here, a "graph" simply means a network made of points (called vertices) connected by links (called edges). The points could represent cities, PCs, metro stations or even organs of the body, and the links could represent roads, cables, tracks, or blood vessels.

Computing exact distances between every pair of vertices in a large graph is costly in terms of time and space. For dense networks, it can take cubic time. In simple words, if the network size doubles, the work increases about eight times, i.e.,work grows much faster than the network grows. Hence, for decades, researchers have hunted for faster approximation algorithms: methods that deliver distances very close to the actual values while running far less time.

How a classic shortcut works...Back in 1996, Dor, Halperin, and Zwick (DHZ) showed that you could get distance estimates no worse than twice the actual value, a "2‑approximation," in nearly optimal time. In simple words, if the real distance is 10 kilometers, their method guarantees an answer between 10 and 20. To do this efficiently, the algorithm operates on a small subset of vertices sampled from the network (referred to as sampled vertices). Instead of exploring every possible route between two vertices, the algorithm relies on the sampled vertices to efficiently estimate distances.

Now, picture estimating travel between Delhi and Chennai: For such long trips, the DHZ shortcut gives a quick, fairly reliable answer. That is, when vertices were far apart, this usually resulted in an estimate no worse than twice the true shortest path, because a sampled vertex was often located near the shortest path between them.

However, for short hops, like two neighborhoods in the Mumbai suburbs, that same shortcut could miss the mark and give a poor estimate. The catch was this: For close pairs, there may be no such guarantee that the method can return a value no more than twice the actual value at times. For instance, if the actual shortest path is two edges long, the estimate using the sampled vertices might be five edges long (i.e., more than 22), which violates the "at most twice" promise. For vertices that were close together, this detour often ended up distorting the result. That limitation persisted for nearly 25 years.

A new multi-scale refinement emerges...A noteworthy refinement to this computation for the closer vertices of massive networks was presented by Dr. Manoj Gupta at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025). He put forth this refinement in the paper titled "Improved 2-Approximate Shortest Paths for close vertex pairs."

Dr. Gupta, an associate professor at the Indian Institute of Technology Gandhinagar, demonstrates that 2-approximate distances can now be efficiently computed for vertex pairs that are much closer than previously thought possible, without increasing overall runtime.

Earlier approaches had relied on sampling representative vertices to help estimate distances.

On the other hand, the new approach introduces a multi-scale refinement of this sampling process, carefully layering information about the graph's structure. Instead of relying on a single layer of sampled vertices, the algorithm organizes them at different scales, so even shorter paths are likely captured more accurately. This enables the algorithm to maintain at least the same time complexity while shrinking the minimum distance threshold for which the 2-approximation guarantee holds. This advance centers on a more brilliant sampling strategy.

In short, the DHZ algorithm worked efficiently but only for sufficiently long distances. In comparison, the new algorithm maintains or improves speed while extending the guarantee to much shorter distances (such as Mumbai's suburbs). That shift in the boundary is the crux of this work.

Why this theoretical advance matters...Why is this important? Large networks are everywhere, from internet routing and transport grids to social platforms and AI systems that use graph data. We often do not need precise distances in the real world, but what we need is speed, scale, and dependable approximations. This is exactly what the new algorithm proposes to provide.

Improving a long‑standing theoretical bound matters for more than theory. It helps us see how global structure can emerge from local connections and brings us closer to the practical goal of computing reasonable all‑pairs distances quickly.

In a field where progress usually comes in very small steps, improving a result that has stood since 1996 is a meaningful leap. Narrowing that gap strengthens the theory behind scalable graph algorithms—the quiet engines that keep many connected systems running smoothly today.

Provided by Indian Institute of Technology Gandhinagar