SSSP: the performance crossover is in the record
Research settingIndependent
The September 2026 study investigates a practical question inside a correct shortest-path solver: how much time is spent managing candidates that will never improve the answer? Its strongest finding is a workload-dependent tradeoff between duplicate suppression, bucket width, and queue overhead.
From the research record
Inspect the work
Original figures, recorded values, and explicit model details. Each exhibit identifies its source and what the comparison means.
What duplicate suppression actually removes
Scroll horizontally to inspect the full table →
| Implementation arm | Vertex scans | Unchanged scans | Heavy-edge work | Total edge scans |
|---|---|---|---|---|
| heavy_only | 29540.5 | 21195.5 | 1249712.0 | 17263035.5 |
| list_both | 29540.5 | 21195.5 | 7383815.5 | 14764482.5 |
| mean_map | 8271.0 | 21195.5 | 1249712.0 | 6630177.5 |
| skip_only | 8271.0 | 21195.5 | 2065777.5 | 4132423.5 |
Dense input, n = 5,000. These are saved aggregate counters, so half-integer values are possible. Compare work counters within this input; they are not elapsed-time speedups.
Read the technical figure
Saved September 2026 density sweep. Playback selects existing cases; it does not rerun a solver. Intervals are descriptive across seeds.
- Mean degree 2
-
Ratio: 0.854857
Lower / upper: 0.297143 / 1.457413
Identical ratio definition across density cases
- Mean degree 4
-
Ratio: 1.689844
Lower / upper: 1.659333 / 1.705570
Identical ratio definition across density cases
- Mean degree 8
-
Ratio: 1.714637
Lower / upper: 1.497648 / 1.863907
Identical ratio definition across density cases
- Mean degree 16
-
Ratio: 1.698374
Lower / upper: 1.641242 / 1.802612
Identical ratio definition across density cases
- Mean degree 32
-
Ratio: 1.369072
Lower / upper: 1.298954 / 1.501383
Identical ratio definition across density cases
- Mean degree 64
-
Ratio: 1.007612
Lower / upper: 0.899148 / 1.116066
Identical ratio definition across density cases
Supporting detail
The experiment is about the queue
The study compares sequential bucket-based implementations with its binary-heap Dijkstra implementation. Mean-width, degree-scaled, and calibrated bucket choices change which tentative distances are processed together. Duplicate suppression tries to avoid paying repeatedly for the same pending work. Full distance-vector agreement is checked separately from timing.
Local lookahead is a second intervention. It asks whether an inexpensive view of nearby graph structure can improve queue behavior. In the reported tests, the tested lookahead features did not demonstrate an insertion benefit. That result matters: the geometric motivation did not translate into acceleration for this mechanism.
A favorable sparse result, an unfavorable dense result
The companion reports a standard-heap-time / method-time ratio of 1.82 for deduplicated cyclic buckets on sparse graphs with one million vertices, and 1.51–1.64 on three DIMACS road networks. The same ratio is 0.564 for deduplicated map buckets on dense graphs with 5,000 vertices. Ratios below one mean the tested method was slower.
These are results for the saved implementations and one machine. They identify an engineering tradeoff rather than an algorithm that dominates every graph family. The useful contribution is the connection between elapsed time and the work the implementation actually performs.
Sources, scope, and next question
Experimental companion with saved timing results and a reproduction artifact.
The next comparison should test whether the duplicate-work explanation survives an independently maintained baseline, with calibration and loading costs reported separately. Repeating only the favorable sparse inputs would miss the main lesson of the study.
- September 2026 research companion.
- Saved timing record.
- Full working paper.
- The Davis Manifold Framework for Single-Source Shortest Paths: Curvature-Aware Graph Algorithms.
Related deposits that are not this study
- 10.5281/zenodo.18284154 Earlier, separate study. The January 2026 deposit applies a degree-based curvature proxy and reports its own comparison; it is not the September 2026 bucket-width companion described on this page, and none of its reported figures are carried here.