Deterministic APSP in O(n^2.996001) time on a word RAM (library form)

All-pairs shortest paths on directed graphs with integer weights and no negative cycles can be solved deterministically in time $O(n^{2.996001})$ 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. The input is the $n\times n$ $0/1$ adjacency matrix followed by the $n\times n$ weight matrix, both row by row. The output has two cells for every pair $(i,j)$: the flag $1$ followed by the distance 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$ with $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. The word RAM has no division, no shift, no bitwise operation and no randomness.

The bound improves the deterministic exponent $2.99791$ of the previous entry. The proof runs in time $n^{2.9960009}$ for large $n$ (savings $2\sigma\Gamma_0=2\sigma(1/2-q_0)\approx0.0039992$ with block size $s=2^{\lfloor0.0284225k\rfloor}$).

This is the library form of the campaign goal TrulySubcubicAPSP.apsp_bound_2996001; 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 (on the platform the definition TrulySubcubicAPSP_SourceSpecification); the exponent is the rational numeral $2.996001$.