All-Pairs Shortest Paths

Take a map of towns with one-way roads, where each road has a cost. The problem is to find the cheapest route between every pair of towns. In mathematics, this map is a graph. A graph is a set of dots, called vertices, joined by lines, called edges. Here the towns are the vertices and the roads are the edges.

The figure shows a small example. The road from $a$ to $c$ costs 7, but going through $b$ costs $1+2=3$. So the cheapest route is not always the direct one.

The textbook method takes each town in turn as a possible stop. For each pair of towns, it checks if a stop there makes the trip cheaper. With $n$ towns, that is $n\times n\times n=n^3$ steps. With 1,000 towns, it is a billion steps. For decades, the only improvements saved less than any fixed power of $n$.

The problem is a kind of table multiplication. A matrix is a table of numbers. Put the road costs in a matrix $A$, with a row and a column for each town. For the cheapest trip from $i$ to $j$ with at most two roads, try each middle town $k$. Add the two costs and keep the smallest:

Here $A[i,k]$ is the entry in row $i$ and column $k$, $\min$ means the smallest value, and the star marks this kind of multiplication. Apply this to $A$ and itself, and you get the cheapest trips with up to 2 roads. Apply it to the result and itself, and you get up to 4 roads, then 8, and so on. A few rounds cover every route. So a fast way to do this one step would solve the whole problem.

This step looks like ordinary matrix multiplication, which multiplies pairs of numbers and adds the results. Here, adding replaces multiplying, and taking the minimum replaces adding. Ordinary matrix multiplication has fast methods that take far fewer than $n^3$ steps. Those methods use subtraction to cancel terms.

The minimum has no such undo. If you only know that the smaller of two numbers is 3, you cannot recover the other number. A program that uses only minimum and addition needs about $n^3$ operations. So any speedup must use other arithmetic.

APSP stands for all-pairs shortest paths. The APSP hypothesis says that no method takes $n^{2.99}$ steps, or $n^{3-\epsilon }$ for any fixed small number $\epsilon$, the Greek letter epsilon. A power does not have to be a whole number, and $n^{2.99}$ is a little less than $n^3$. Many other problems are equally hard, such as finding three towns whose triangle of roads has a negative total cost. All of them get faster, or none of them do.

Josh Alman and Virginia Vassilevska Williams report that the hypothesis is false. Their method takes $n^{2.9995}$ steps, for whole-number costs no larger than a fixed power of $n$. Claude discovered the method. It also gives a faster method for 3SUM, a puzzle that asks if three numbers in a list add up to 0. With a million towns, $n^{2.9995}$ is less than 1% below $n^3$. The step count also leaves out a fixed multiplier, which is enormous, so this changes the theory and not practical route finding.