Algorithms & computing / SSSP
SSSP: where bucket scheduling saves work—and where it loses
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.
Research settingIndependent
TL;DR
In brief
The question
When a shortest-path solver groups pending distances into buckets instead of keeping a strict heap order, when does the saved ordering work outweigh the extra candidates it handles?
What the work does
Rust implementations of bucket-based Δ-stepping variants and a binary-heap Dijkstra, timed on synthetic graphs and three DIMACS road networks: 192 configurations, 53,460 timed runs, one machine, distances checked.
What is still open
Whether the duplicate-work explanation holds against an externally maintained solver, on other machines and graph families, with calibration and loading costs reported separately.
Available recordExperimental companion with saved timing results and a reproduction artifact.
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.
The research in context
Single-source shortest paths asks for the least-cost distance from one starting vertex to every other vertex of a weighted network. Dijkstra’s algorithm settles vertices strictly in distance order, usually with a binary heap whose operations cost logarithmic time. Δ-stepping relaxes that order: it groups tentative distances into buckets of width Δ and processes a whole bucket at once, trading cheaper queue operations for the risk of examining a vertex again after its distance improves. The width is the difficult choice. Too narrow, and buckets add overhead without saving ordering work; too wide, and the solver repeats work a heap would have avoided.
The study, Bucket Width, Duplicate Work, and Local Lookahead in Sequential Shortest Paths (Draft v3, September 2026), implements every solver in Rust, including the heap baseline. Width rules include the mean edge weight, a maximum-degree rule documented by Boost (reimplemented in the study’s harness, not a run of Boost itself), and a calibrated rule that tries 12 widths from a separate source vertex. A factorial ablation switches off rescans at unchanged labels and repeated heavy-edge relaxations independently. Inputs are synthetic sparse, dense and grid graphs plus the New York, Bay Area and Colorado DIMACS road networks (264,346 to 435,666 vertices), run on an Intel Core i7-13620H with one software thread.
A degree sweep shows how narrow the favorable range is. With graphs held at 5,000 vertices and the mean width with ordered buckets, the ratio of heap time to method time is roughly 1.7 for expected out-degrees of 4 to 16, about 1.37 at degree 32 and 1.01 at degree 64, and below one at 128 and 256 (0.78 and 0.65); at degree 2 the seed-to-seed range spans both sides of one. The study also stored the graphs in GIGI, the author’s Rust database engine, which preserved them and their distances through storage and reload; a GIGI-derived admission rule reduced heap insertions in 0 of 72 tested queries.
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.
Inspect the project record
The next research step
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.
Background mathematics and definitions
Use a directed graph with nonnegative edge weights and one source. Every implementation receives the same adjacency data. A relaxation replaces a tentative distance only when a route through the current vertex is shorter. Buckets group tentative distances into intervals; their width changes queue behavior rather than the path-length definition.
- d(v)
- Current tentative distance from the source to vertex v.
- w(u,v)
- Nonnegative edge weight in the supplied graph.
- Δ
- Bucket width; a scheduling parameter, not a modification of edge weights.
Illustrative example
In an illustrative graph, s→a costs 2, a→t costs 3, and s→t costs 8. The best route to t costs 5. An implementation may first enqueue 8 and later enqueue 5; the example distinguishes a correct answer from the amount of duplicate work used to reach it.
This background example is separate from the source records and the main technical figure.
Source record
- 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.
No new experiments are reported in this research note. Figure captions distinguish saved research records, source-model calculations, and explanatory diagrams.