Deterministic APSP in $O(n^{2.99791})$ time on a word RAM

All-pairs shortest paths on directed graphs with integer weights and no negative cycles can be solved deterministically in time $O(n^{2.99791})$ on a word RAM with $O(\log n)$-bit words:

The problem. An instance of size $n$ is a directed graph on the vertices $0,\dots,n-1$ given by a partial weight function $w$: $w(i,j)\in\mathbb Z$ is the weight of the edge $i\to j$, or undefined if there is no such edge. Instances have no negative cycle: every closed path has total weight at least $0$. The input is the $n\times n$ $0/1$ adjacency matrix followed by the $n\times n$ weight matrix (with $0$ where there is no edge), both row by row. The output has two cells for every pair $(i,j)$: the flag $1$ followed by the distance $d(i,j)$ (the weight of a path from $i$ to $j$ that is at most the weight of every such path) if $j$ is reachable from $i$, and the flag $0$ otherwise.

The machine and the time bound. $Q.\mathrm{SolvedInTime}(r)$ means: for every $\kappa\in\mathbb N$ there are a program $P$ of the word RAM, a number $b$ and a function $T:\mathbb N\to\mathbb N$ with $T(n)=O(n^{r})$ (precisely, $T(n)^{\mathrm{den}\,r}\le K\,n^{\mathrm{num}\,r}$ for some $K$ and all $n\ge2$) such that on every instance of every size $n$ whose input numbers have absolute value at most $n^{\kappa}$, and for every word size $W\ge b\,(\lfloor\log_2 n\rfloor+1)$, the program halts within $T(n)$ steps, accepts, and leaves the correct output in the cells right after the input. The word RAM has nine instructions (write the constant $1$; add, subtract or multiply modulo $2^W$; load; store; jump if negative; accept; reject); there is no division, no shift, no bitwise operation and no randomness.

The bound improves the deterministic exponent $2.99942$ of Theorem 22 of Alman and Vassilevska Williams. The algorithm saves $\delta=143/68400$, so $3-\delta\approx2.9979094<2.99791$; the margin absorbs the polylogarithmic factors.

This is the library form of the campaign goal TrulySubcubicAPSP.apsp_bound_299791; the platform node TrulySubcubicAPSP.sourceSpecificationTransport carries it over to the campaign's own definitions.

Formalization Note APSP and Problem.SolvedInTime are those of the namespace EndStatement (the library file EndStatement.lean, on the platform the definition TrulySubcubicAPSP_SourceSpecification); the exponent is the rational numeral $2.99791$.