Faster way to compute shortest paths in big networks

Simple, Faster (min, +) Matrix Multiplication and APSP

Data Structures and Algorithms

Summary

Finding the shortest routes between all points in a large network is a key problem in computing. The authors improved the time needed to do this calculation using a new method that breaks the problem into phases. Their approach finds an approximate solution quickly and then efficiently fixes the remaining errors using a new mathematical tool. This leads to a faster algorithm for computing shortest paths between all pairs of nodes in a network.

What this means in practice

  • For network engineers: Enable faster computation of shortest routes in large communication or transportation networks using the improved shortest paths algorithm.
  • For database system developers: Implement more efficient query planning by using faster shortest path calculations within relational or graph databases.

A theory result. No direct application yet.

Authors

Barna Saha, Christopher Ye

Abstract

In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.