Binary-heap Dijkstra
Minimum-label extraction0 candidate checks1 finite labels
Bucket Width, Duplicate Work, and Local Lookahead in Sequential Shortest Paths
Abstract
We compare mean-edge-weight Δ-stepping, degree-scaled width rules, and source-calibrated widths in a common sequential setting. A factorial experiment separates unchanged-label rescans from repeated heavy-edge processing. The unchanged append-only implementation reaches a paired speed ratio of 1.97 on sparse graphs with 10,000 vertices; a deduplicated cyclic implementation reaches 1.82 at one million vertices and 1.51–1.64 on three DIMACS road networks. Duplicate suppression substantially reduces dense-graph overhead, while the heap remains faster. Matched controls find no insertion benefit from degree-gated lookahead in 24 live core queries. This companion exposes recorded timings and executable small-graph traces; the latter are explanatory and are not benchmark measurements.
Keywords: single-source shortest paths; Δ-stepping; bucket width; duplicate suppression; experimental algorithms.
| Input | Vertices | Implementation | Speed ratio |
|---|
Paired ratios aggregate across held-out sources and graph seeds. The baseline is the author’s Dijkstra using Rust’s standard-library binary heap. These results do not establish a distribution-independent ranking.
1. Recorded measurements
Per-query timing comparison
Select a configuration, seed, source vertex, and validation round. The display reconstructs relative completion times from saved measurements; it does not rerun the benchmark.
Recorded durations / normalized display time
Ready to replay.
Input geometry and source-distance propagation
Geometry provenance Input edges Revealed by distance Current distance band Source vertex
The networks fill outward from the selected source. Geometry comes from fingerprint-verified benchmark inputs; road positions use DIMACS coordinates. Color reveals recomputed final shortest-path distances, scaled to each saved finish time. This is an illustrative distance wave, not a logged execution trace or a measurement of work completed. Layout and sampling are shared across implementations.
Figure 1. Recorded solve durations from a common validation round, linearly rescaled for display. Bar length encodes elapsed time, not internal work completed. Arms were measured separately in balanced order. Graph loading and most preparation are excluded.
Aggregate comparison
Implementation definitions and accounting
Heap / Dijkstra: extract the minimum tentative-distance label using a binary heap with lazy deletion and settled flags.
List: the author’s unchanged mean-width solver. It can keep duplicate work in its lists.
Map / Ring: use the mean link cost as the group width and suppress duplicate work. Map uses ordered buckets; Ring uses a cyclic bucket array.
Max / degree: another cheap width rule, documented by Boost and tested here in the study’s Map solver. It is not a run of Boost itself.
Calibrated: try 12 widths using a separate starting vertex, then measure the chosen width on held-out queries. The displayed solve duration excludes calibration cost.
2. Algorithm traces
Label ordering and bucket closure
Dijkstra extracts a minimum tentative label. Δ-stepping closes the smallest occupied distance interval under light-edge relaxations, then processes heavy edges at final labels for that phase.
Deduplicated Δ-stepping
Light closure / heavy scan0 candidate checks1 finite labels
Unreached Finite label Active vertex Successful relaxation
Figure 2. Executable traces on a 12-vertex illustrative graph. Each step advances one displayed event per solver, not an equal wall-clock interval. Vertex annotations give tentative distances; highlighted arcs indicate successful relaxations. Candidate checks count evaluated relaxation candidates. These traces are separate from the Rust timing campaign.
3. Sensitivity and mechanism controls
Dependence on out-degree
The degree sweep varies expected out-degree while holding n = 5,000. Mean-width stepping trades heap ordering against bucket work; its measured advantage is limited to part of this range.
Measured degree sweep · 5,000 vertices · mean width + Map
1.71×
3.1 Duplicate-work ablation
Unchanged labels and repeated heavy relaxations
Independent controls suppress light scans at unchanged labels and deduplicate heavy work within a phase. Counts below use the same mean width and map container on dense graphs at n = 5,000.
Dense-input speed ratios: List 0.063; Map 0.564.
The corresponding durations are approximately 15.9 and 1.77 times the standard-heap baseline. Suppression reduces the slowdown but does not reverse the ranking.
4. Lookahead and graph-derived features
GIGI (Geometric Intrinsic Global Index) is the author’s Rust database engine. It organizes keyed records into bundles, separating identifying and indexed base fields from associated fiber values, and provides statistical and geometric queries over those records. In this study it stores weighted arcs, exposes indexed incidence, and supplies the normalized weight-variance feature; the timed solvers use extracted adjacency lists. Source code and documentation are available under the PolyForm Noncommercial License 1.0.0.
Degree-gated lookahead
No live core query used fewer heap insertions with degree-gated lookahead. It was more selective than unrestricted scouting, but never beat doing no scouting in the measured query medians.
GIGI low-K admission
It never reduced insertions versus no lookahead. GIGI successfully preserved the graph and its distances through storage and reload; the tested geometric features added no demonstrated acceleration.
5. Reproducibility and scope
Artifact, protocol, and limitations
The study concerns sequential execution on one machine with three synthetic seeds per setting. Competing search-free rules perform comparably on the road inputs. The measured operating range is implementation- and distribution-dependent.
192graph configurations
53,460primary timed runs
3synthetic seeds per setting
1machine, one software thread
Measurement definitions and limitations
- The headline ratios aggregate paired measurements across sources and seeds. They need not equal a ratio calculated from two displayed median times.
- The replay uses individual saved rounds. Individual outcomes vary; use the aggregate results to interpret the study.
- 43,956 timings are validation measurements; 9,504 are width-calibration measurements. Configurations include transformations of shared graphs, not 192 independent topology draws.
- Reported solve times exclude graph loading and most preparation. List computes its mean inside each solve. Calibrated widths exclude their tuning cost in the race.
- The timing baseline and all competing solvers are the study’s own implementations. Boost’s documented rule was implemented in this harness; no externally maintained solver was timed.
- Complete distance vectors were checked with a stated numerical tolerance. The three-seed uncertainty bands are descriptive, not broad population guarantees.
- The machine was an Intel Core i7-13620H with 64 GB RAM, Windows 11, and Rust 1.92.0. Hardware, graph structure, and implementation can change the outcome.
- The separate layout summary excludes one case affected by reported synchronization interference. This page does not use the layout panel for its races or headline claims.