All-pairs shortest paths complexity

Three places have direct travel costs A–B: 3, B–C: 4 and A–C: 10. Going from A to C through B costs 7, so the direct connection is not the cheapest route. All-pairs shortest paths asks for the cheapest cost between every pair of places in a network. Can one exact algorithm handle every allowed network with a growth rate below the familiar cubic rate, where doubling the number of places multiplies the main work by eight?[2]

Can we compute the exact cheapest route cost between every pair in a general weighted network with a fixed-power improvement over cubic time? Let $n$ count vertices and let $D_{ij}$ store the current cost from $i$ to $j$. The Floyd–Warshall method considers intermediate vertices one at a time, updating $D_{ij}\leftarrow\min(D_{ij},D_{ik}+D_{kj})$ for each pair. Each stage permits one more intermediate vertex in a route. There are $n$ stages and $n^2$ pairs, giving cubic work. The target is $O(n^{3-\varepsilon})$ for a fixed $\varepsilon>0$, on general integer weights whose magnitudes are bounded by a fixed power of $n$, with no negative cycle—a cost-reducing loop. Unreachable pairs can be marked as having infinite distance.[1] [2]

The saving must persist as networks grow: for example, work growing like the number of places to the power 2.9 would qualify, but merely halving a cubic running time would not. The question allows whole-number connection costs whose magnitudes grow at most as some fixed power of network size. It excludes cost-reducing loops that make a cheapest route undefined. Neither the required general algorithm nor a proof that it is impossible is known.[1] [2]

Known savings over cubic time need not reduce its power by a fixed amount. The APSP hypothesis asserts that the required truly subcubic algorithm does not exist in the standard general setting; that is a hypothesis, not a proved lower bound. Fischer’s 2026 equivalences use additional assumptions, including a matrix-multiplication condition and an additive-combinatorics assumption. Polak and Schmidt’s algorithm always returns exact answers, but its faster bound depends on the quality of the supplied predictions and can revert to cubic work in the worst case.[1] [2]

An exact distance table lets later queries ask the cheapest cost between any two places without solving a new route problem each time. It is also a benchmark for other computations: researchers can transform instances of one task into another and compare their running times. This can explain why improving a familiar network calculation would improve several other tasks that already have polynomial-time algorithms.[1] [2]

A fine-grained reduction preserves enough information about running time that a faster solver for the target would produce a faster solver for the source. It can therefore transfer an APSP-based conditional barrier to another task, or make a new algorithm useful beyond shortest paths. The intellectual payoff is a more detailed map of efficient computation: two tasks can both be polynomial-time solvable while their best attainable powers remain linked in a nontrivial way.[1]