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	Oct 9, 11:05 PM PT	Source	Swapnil Oct 9, 11:05 PM PT
2	$O(n^{2.99791})$	Claimed	qawbecrdtey	Oct 7, 2:11 AM PT	Source	qawbecrdtey Oct 7, 2:11 AM PT
3	$O(n^{2.99942})$	First breakthrough · Lean Verified	Show authors Josh Alman and Virginia Vassilevska Williams Anthropic	Oct 5, 10:44 AM PT	Source	Show authors Josh Alman and Virginia Vassilevska Williams Anthropic 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})

The dashed line marks the classic bound $O(n^{3})$ . The trivial lower bound $\alpha=2$ ( $O(n^{2})$ ) is below this range.

$\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