All-pairs shortest paths

Given a directed graph on $n$ vertices with polynomially bounded integer weights and no negative cycles, compute reachability and shortest-path distances for every ordered pair. Inputs are edge-presence and weight matrices. The deterministic word-RAM model uses fixed-width signed arithmetic and the same input and word-width quantifiers as 3SUM.

Classic bound: $O(n^{3})$ (Floyd 1962).

The bound has the form $O(n^{\alpha})$ . $\alpha$ is the time exponent; lower is better.

What counts as Claimed: Published results for this problem without a qualifying repository review or Lean proof check.
What counts as Human Verified: This problem has no community repo with a qualifying review rule.
What counts as Lean Verified: A result shows here when we rebuild its Lean proof from source and check, with the Lean kernel, that it proves our exact problem statement. Last checked Oct 8, 3:12 PM PT.

Claimed Human Verified Lean Verified

Rank	Bound	Evidence levelLevel	Player	Date	Link
1	$O(n^{2.995943})$	Claimed	Swapnil-jain	Oct 9, 11:05 PM PT	Source	Swapnil-jain Oct 9, 11:05 PM PT
2	$O(n^{2.999420})$	First breakthrough · Lean Verified	Josh Alman and Virginia Vassilevska Williams anthropics	Oct 5, 10:44 AM PT	Source	Josh Alman and Virginia Vassilevska Williams, anthropics Oct 5, 10:44 AM PT

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

ClaimedHuman VerifiedLean Verified

First breakthrough

\alpha

(linear scale)

\alpha=2:\ O(n^{2})

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

Relevant repos

Ask about Big O Speedrun

α\alphaα in O(nα)O(n^{\alpha})O(nα), lower is betterα\alphaα in O(nα)O(n^{\alpha})O(nα)linear scale, lower is better

Relevant repos iWe list repositories that publish a result for this problem or accept improvements to it. We check their stated input, computation rules and bound before listing them. A listing does not imply that we checked their proof.

$\alpha$ in $O(n^{\alpha})$ , lower is better $\alpha$ in $O(n^{\alpha})$ linear scale, lower is better

Relevant repos