Breaking the Sorting Barrier for Directed SSSPRan Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui YinSTOC 2025 · arXiv 2504.17033 · tested 2–3 Oct 2026
Read paper ↗
A Faster Directed SSSP AlgorithmRan Duan, Xiao Mao, Xinkai Shu, Longhui YinPreprint · arXiv 2602.07868 · tested 2–3 Oct 2026
Read paper ↗
A Faster Undirected SSSP AlgorithmAvi Kadria, Liam RodittyPreprint · arXiv 2609.15247 · tested 2–3 Oct 2026
Read paper ↗

Are new shortest-path algorithms faster than Dijkstra?

Not on real road maps.

On four US maps, the measured implementations were 6–75× slower than direct Dijkstra; 1,600 / 1,600 quiet-server runs returned certified distances.

1 confirmed1 fine print3 not confirmed1 couldn't test

The idea, in 8 seconds

Dijkstra0
Duan 20250
NY road map · time scaledEdge visits, illustrative animation
MEASURED RESULT · NY ROAD MAPDijkstra 28.5 ms · KR 2026 7.4× · Duan 2026 35.0× · Duan 2025 73.5×50 paired sources · quiet server · ratios rounded from CSV

The verdicts

Tap any card

What we found in the papers

Tap an issue for the second review

Watch the gap open up

50 paired runs per map · min–max whiskers

1×10×100×

Median time divided by binary-heap Dijkstra on the same source. Position is logarithmic; outlined whiskers show minimum to maximum paired ratios.

Work done

Instrumented operations relative to Dijkstra

Bar length is log-scaled. These are method-specific counter proxies: Dijkstra and Duan 2025 relaxations, Duan 2026 edge scans, and the KR pipeline's three reported relaxation phases. They are not identical units or complete cost accounting.

Lab notebook

Expert view

CSV-derived figures · 50 paired sources per map

Fig. 1 Quiet-server road results

Paired median slowdown [minimum–maximum] over five seeds and ten sources for each map. The baseline is binary-heap Dijkstra; all 1,600 / 1,600 road rows passed distance certification. NY CSV · BAY CSV · COL CSV · FLA CSV.

Fig. 2 Laptop vs quiet server

MethodShared laptopQuiet server
Duan 202583.7–125.5×70.6–75.0×
Duan 202646.4–66.5×33.2–39.5×
KR pipeline8.5–12.4×6.3–7.4×
The laptop was shared and had no timed-run warm-up. The quiet EPYC-Rome server used a dedicated core, warm-up and rotated algorithm order. The earlier study arXiv 2511.03007 reported 3–4× for its 2025 implementation; direction agrees, magnitude does not.

Fig. 3 Correctness and scope

1,600 / 1,600 certifiedFour maps · five seeds · ten sourcesNonnegative integer weights · exact distance oracle
Certification checks tested outputs, not the papers' real-weight comparison-addition bounds. Validation CSV and run metadata.

Fig. 4 Synthetic component scaling

Log–log slopes fitted to four sizes (n = 100, 300, 1,000, 3,000) from full_synthetic.csv, full_synthetic_extra.csv and full_synthetic_scale.csv. They are component counters, not full running-time bounds; substitutions and finite sizes limit the inference.

Reproduce Exact benchmark and analysis commands

target/release/bench.exe --algos all --graphs NY,BAY,COL,FLA --seeds 1,2,3,4,5 --sources 10 --repeats 1 --warmup 0 --output results/full_roads.csv
python tools/plot.py
powershell -ExecutionPolicy Bypass -File tools/run_all.ps1
These are the recorded laptop snapshot and analysis commands from the source repository. The quiet-server invocation and hashes are in vps.meta.txt. Re-running timing on another machine will give different times.

How we checked

What each check can establish

Case 003 / findings / 3 October 2026

What the measurements show

Not on four real US road maps in our implementations. Every one of 1,600 quiet-server road runs returned certified distances, but road-map medians were about 6–75× slower than direct Dijkstra. These timings do not test the papers' asymptotic bounds.

Original research: Duan, Mao, Mao, Shu & Yin (STOC 2025) · Duan, Mao, Shu & Yin (2026) · Kadria & Roditty (2026). Full author credits below.

Tested 2–3 October 2026Published 2026-10-03Raw CSV below

Paired median wall-clock slowdown relative to direct binary-heap Dijkstra on each map. Logarithmic scale. KR pipeline includes Dijkstra black-box substitutes.

What the data says.

This table contains the measured comparison behind the answer. The expert sections below explain how the numbers were produced and what they cannot establish.

Swipe to see all columns →

Road mapDuan 2025Duan 2026KR pipeline
NY73.5×
60.8–81.5×		35.0×
28.3–39.3×		7.4×
6.3–8.6×
BAY72.4×
62.0–83.6×		33.2×
28.1–37.1×		6.6×
5.5–7.4×
COL70.6×
57.0–75.2×		36.6×
29.3–40.5×		6.3×
5.0–6.9×
FLA75.0×
67.4–81.7×		39.5×
35.7–43.1×		6.9×
6.2–7.7×

Each small range is the minimum to maximum across the 50 paired seed–source ratios for that map.

Claim-by-claim verdicts.

Confirmed means supported within the stated test; Partly confirmed keeps a tested piece separate from an untested part. Not confirmed means the tested evidence did not show the claim. Could not test marks missing evidence or an inapplicable setup.

Swipe to see all columns →

ClaimVerdictEvidence boundary
Certified distances on tested graphsConfirmed1,600/1,600 quiet-server road rows passed certificates.
Duan 2025 faster on these road mapsNot confirmedIts measured implementation was slower on each map.
Duan 2026 faster on these road mapsNot confirmedIts measured implementation was slower on each map.
Kadria–Roditty pipeline faster hereNot confirmedThe substituted pipeline was slower on each map.
The papers' asymptotic boundsCould not testChanged data structures and black boxes, finite graphs, and astronomical crossover scales.
Paper algorithm correctness in generalPartly confirmedOutput certificates passed for tested nonnegative integer graphs only.

Expert detail: measurements and interpretation

The comparison pairs each paper-implementation time with the selected direct Dijkstra time on the same seed and source. Each road map contributes 50 paired sources across five seeds. The selected Dijkstra variant is binary heap on every map. “KR practical” is itself a direct binary-heap Dijkstra; it is a baseline, never the Kadria–Roditty paper method. The plotted KR pipeline has Dijkstra substituted for two cited black boxes. The directed implementations also replace some queues or maps whose amortized costs matter to the proofs.

An earlier independent implementation study of the 2025 method, arXiv 2511.03007, reported only a 3–4× slowdown. Our 71–75× 2025 road gap therefore partly reflects our less-optimized implementation and different setup. The magnitude is not a replication. Road weight conventions also differ. These timings come from one dedicated quiet AMD EPYC-Rome server core, with a warm-up before every timed run and algorithm order rotated across sources; the earlier laptop run, shared with other agents, gave larger and noisier ratios and remains in the downloadable data for transparency.

Laptop vs quiet server: ranges below span the four road-map medians for each method. The earlier source-level ratios also varied more widely.

Swipe to see all columns →

MethodShared laptopQuiet server
Duan 202583.7–125.5×70.6–75.0×
Duan 202646.4–66.5×33.2–39.5×
KR pipeline8.5–12.4×6.3–7.4×

Quiet-server binary-heap Dijkstra medians: NY 28.5 ms, BAY 32.5 ms, COL 46.3 ms, FLA 116.1 ms.

All full benchmark distances passed an independent certificate. The tests used nonnegative integer graph weights, while the theorems address real-weight comparison-addition models. Our finite implementation timings cannot test or refute big-O guarantees at astronomically large input sizes. Component counters and small synthetic fits remain exploratory. The complete road and synthetic run CSVs are linked below; each is under five megabytes.

How we tested

We implemented each algorithm in Rust, calibrated direct Dijkstra baselines, checked graph outputs against a distance oracle and certificate, and ran paired source comparisons on New York, Bay Area, Colorado and Florida road graphs. The quiet-server sweep used five seeds and ten sources per map, plus synthetic families. The data files preserve every full run, along with the earlier laptop sweep and its paired summaries.

Limitations and next check

The implementations substitute data structures and two Kadria–Roditty black boxes. They therefore cannot test or refute the papers' big-O results. The prior independent 2025 study found only a 3–4× slowdown, so our much larger gap is implementation-sensitive. The quiet-server timings and the earlier shared-laptop timings are both available below.

Issues we found in the papers

Our agents flagged these while building the algorithms. A second, independent reviewer then re-derived each one from the original PDF, with its own code. None of them changes the computed distances or the papers’ main theorems. We have not yet heard from the authors. Reproducers: repro.py (with dmsy25.py and dmsy26.py) and kr_tie_check.py.

Minor wording: Duan et al. 2025, Lemma 3.3. The text says an overfull block is split into two blocks of “at most ⌈M/2⌉” elements. For even M, M+1 elements cannot fit that way. The paper’s own median split gives about M/2 each, which is all the proof needs. No effect on results.

Known proof gap, already reported: Duan et al. 2025, Section 3.2. As printed, two sibling recursive calls can return the same vertex: a stale queue entry survives after a child call finishes that vertex (7-vertex example in repro.py). Distances stay correct. The earlier independent study (arXiv 2511.03007) reported this first, with a one-line fix it says the authors confirmed. With the fix, the running-time proof holds.

Proof gap, fixable: Duan et al. 2026, Lemma 3.8. The same mechanism affects the 2026 paper. Its disjointness claim (and the remark “Ui is not in D, no need to remove”) fails for the algorithm as printed (12-vertex example). Distances stay correct. Removing completed vertices from the parent queue fixes it, and the main theorem is not affected.

Small slip, fixable: Duan et al. 2026, Algorithm 4. The apparent “B” mix-up was only a text-extraction artifact: the PDF clearly writes B′ and B. Separately, the base case as printed can return a boundary that is too high when it stops early, which contradicts Lemma 3.7(2) (11-vertex example). Distances stay correct. Returning the smallest remaining queue value fixes it.

Minor, fixable: Kadria & Roditty 2026, Lemma 4. When two samples are equally close, the paper’s super-source procedure can pick a different “nearest sample” than its own definition specifies (5-vertex example; 23 of 3,000 random small graphs). So Lemma 4 is false as written. Distances and the main running-time result are unaffected, and comparing the sample ID before the predecessor ID during relaxation fixes it at no extra cost.

Original sources, data and corrections

The ideas and original claims belong to the paper authors. Kael Research is responsible for these implementations, checks and interpretations. Original source: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (arXiv v2 2025-07-30; STOC 2025)
By Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin
A Faster Directed Single-Source Shortest Path Algorithm (2026-02-10)
By Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin
A Faster Undirected Single-Source Shortest Path Algorithm (2026-09-14)
By Avi Kadria, Liam Roditty. Download each public CSV below; the full experiment repositories, including any larger uncopied raw artifacts, are available on request. For corrections, see our public log or contact us through the site.

Quiet-server run files and metadata, followed by the preserved laptop files:

vps_roads_NY.csv ↧vps_roads_BAY.csv ↧vps_roads_COL.csv ↧vps_roads_FLA.csv ↧vps_synthetic.csv ↧vps_synthetic_scale.csv ↧vps.meta.txt ↧comparisons.csv ↧validation.csv ↧full_roads.csv ↧full_synthetic.csv ↧full_synthetic_extra.csv ↧full_synthetic_scale.csv ↧prior_study_context.csv ↧

Got a paper? We'll test it.

Papers: Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin, “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths”, STOC 2025; Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin, “A Faster Directed Single-Source Shortest Path Algorithm”, arXiv 2602.07868; Avi Kadria, Liam Roditty, “A Faster Undirected Single-Source Shortest Path Algorithm”, arXiv 2609.15247. Ideas and theorems belong to the authors; implementations and measurements here are ours. Tested 2–3 October 2026.