Shortest path algorithm improved after nearly three decades

Manoj Gupta, an associate professor at the Indian Institute of Technology Gandhinagar, has successfully improved the classic All-Pairs Shortest Paths algorithm. Presented at the FOCS 2025 symposium, this result shifts the boundary for guaranteed 2-approximation for the first time since 1996, ensuring that distance estimations do not exceed twice the real value even for much closer network nodes.

• The first major improvement to the classic APSP method since 1996.
• Guaranteed 2-approximation now reliably works for close network nodes.
• Computational speed remains unchanged without increasing complexity.

Historical context and limitations of the 1996 method

Back in 1996, researchers Dor, Halperin, and Zwick proposed an efficient method using a small set of landmark points to quickly estimate long routes without checking every path. However, for close points, these landmarks often ended up far from the shortest connection, causing the algorithm to output longer paths and violate the twice-the-actual-distance guarantee.

Multilevel network representation and Gupta's solution

Gupta completely redesigned the landmark selection process by organizing a multilevel network representation instead of a single layer, analyzing connections across multiple scales simultaneously. This prevents the algorithm from missing short routes that the previous method ignored, successfully expanding the accuracy guarantee zone without adding computational complexity.

Computational complexity and practical importance

The significance of this achievement extends far beyond basic navigation applications. The APSP problem lies at the core of analyzing transport systems, telecommunication networks, and biological structures ranging from protein interactions to neural connections. Since exact calculations on large graphs require cubic time, approximation methods combining speed and controlled accuracy are critically important.

Theoretical impact and future outlook

Although this research is theoretical in nature and is not directly integrated into mapping services yet, it significantly strengthens the mathematical foundation of methods designed to efficiently handle growing networks. Resolving a problem that persisted for nearly three decades represents a major milestone in algorithm theory.