Manoj Gupta Breaks a 1996 Barrier in Shortest-Path Algorithms

Manoj Gupta of the Indian Institute of Technology Gandhinagar has developed an algorithm that overcomes a limitation which has stood in computer science since 1996. The method gives more accurate approximations of shortest paths between points that lie close together, and it does so without increasing computation time.

Shortest-path calculation is something computers do every day. Navigation apps, transport systems and internet infrastructure all rely on it. The task becomes far harder when distances must be found between every possible pair of points in a very large network, a problem known as All-Pairs Shortest Paths (APSP). A network here is simply a set of points linked by relationships, and those points can stand for cities, computers, railway stations or even neurons.

The 1996 limitation

Calculating every exact route in a large, densely connected network demands enormous computing resources. Researchers have therefore long looked for ways to get reliable results without checking every path. In 1996, Dor, Halperin and Zwick presented an algorithm that guarantees an estimate no larger than twice the real shortest distance, known as a 2-approximation.

The weakness was that the guarantee held mainly for points far apart. For short connections the error could be larger: a real route of two links might be estimated as five, which breaks the twofold margin.

What Gupta changed

Gupta improved how the points used for estimation are chosen. The earlier approach relied on a relatively small set of representative vertices. The new algorithm uses multi-scale sampling, meaning it examines the network's structure at several levels instead of depending on a single set of points.

This lets the method account for shorter connections that were previously missed. Crucially, the gain in accuracy does not raise the algorithm's overall computational complexity, so results are more reliable at no extra running-time cost.

The work could matter wherever large networks are analyzed, including telecommunications, transport, social media and artificial intelligence systems. In each, fast and dependable distance estimates help analyze dependencies and optimize how entire systems operate.