Randomized Multi-Quantile Bucketing with Lazy Rounds: Exact SSSP in Near-Linear Time in the Comparison + Addition Model

Randomized Multi-Quantile Bucketing with Lazy Rounds: Exact SSSP in Near-Linear Time in the Comparison + Addition Model Anherutowa Calvo October 23, 2025 Abstract We give a simple randomized algorithm for single-source shortest paths (SSSP) on directed graphs with nonnegative real edge weights in the standard comparison + addition model. The algorithm, Randomized Multi-Quantile Bucketing with Lazy Rounds and Verification (RMQBLRV), organizes tentative distances into K = Θ( log n ) independently shifted geometric bucketings and processes the globally minimum bucket index across shifts. Two disciplined mechanisms yield a clean analysis: (i) a multiplicative guard band separates significant from minor improvements, and (ii) a lazy admission rule inserts a vertex into all shifts when any shift’s boundary is crossed, coalescing minor churn. Crucially, we make the algorithm label-correcting with verification: a popped vertex is finalized only after verifying all in-edges; otherwise it is re-admitted. We prove that RMQB-LRV returns exact distances and performs O ( m + nlog U ) successful relaxations and O ( m + nlog U ) bucket operations, where n = |V| , m = |E| , and U is the numeric spread between first finite labels and final distances. For sparse graphs ( m = Ω( n )) and polynomial numeric spread ( U≤nO(1) ), this is ˜ O ( m ) time. The proof uses a deterministic potential over shifted bucket indices and geometric-scale accounting for relaxations. 1 Introduction We study SSSP in directed graphs with nonnegative real weights in the comparison + addition model. Dijkstra with a heap is O ( m + nlog n ). Recent progress reduced worst-case deterministic bounds yet still falls above linear. We present a randomized algorithm that exactly computes distances and runs in near-linear time (up to nlog U) against an oblivious input. Our design is intentionally simple: independent random shifts create K = Θ( log n ) geometric bucket discretizations; we process the minimum nonempty index B over all shifts, with lazy readmission on small changes. To ensure correctness (since earlier buckets may reappear), we add a cheap verification step on pop: if an in-edge can reduce the label, we lower it and re-admit; otherwise we finalize. Contributions. • An exact randomized SSSP that is label-correcting (with verification) and near-linear in the comparison + addition model. • A transparent analysis with: (i) correct constants for bucket-index movement under significant improvements; (ii) a deterministic potential function over shifted indices to amortize admissions; (iii) rigorous event counting; and (iv) geometric-scale accounting proving O ( m + nlog U ) successful relaxations. 1 2 Model and Notation Let G = ( V, E, w ) be a directed graph with |V| = n , |E| = m , w : E→R≥0 , and source s∈V . Denote by d∗ ( v ) the exact distance from s to v . The algorithm maintains tentative labels dist : V→ [0 ,∞ ], initialized by dist ( s ) = 0 and dist ( v ) = ∞ for v = s . A relaxation of ( u→v ) sets dist(v)←min{dist(v),dist(u) + w(u, v)}. Numeric spread. For vertices v with d∗ ( v ) > 0, let dist0 ( v ) be v ’s first finite label during the run. Define U:= max v:d∗(v)>0 dist0(v) d∗(v). All bounds depend on log Uin the standard way for real-weight, comparison-based analyses. Notation. We write ˜ O(·) to hide polylogarithmic factors in n. 3 Algorithm RMQB-LRV Fix constants 0 < γ ≤1 8 and δ := γ/ 4. Let K := clog n for a sufficiently large absolute constant c . Independently sample shifts θ1, . . . , θK∼Unif[0,1). Shifted geometric buckets. For x > 0 and shift i∈ [ K ], define bi ( x ) := ⌊log1+γx + θi⌋∈Z and intervals Ii[k] := (1+γ)k−θi,(1 + γ)k+1−θi. For x= 0 use a dedicated zero bucket. Global current index. Let B:= min i∈[K]min{k∈Z: bucket (i, k) nonempty }. Significant vs. minor improvements. A decrease x→x′ is significant if x′≤ (1 −δ ) x , else minor. Rounds and freezing (lazy admission). The algorithm runs in rounds r = 0 , 1 , 2 , . . . . At the start of each round, set distfrz(v)←dist(v) for all v. What we count as a bucket operation. We model the K shifted bucketings as a single logical scheduler: •Admission: one logical insertion that updates the shared handle. •Pop: removes vat the global index B(deduplicated across shifts). •Rebucket: part of admission; cost O(1). 2 Verification scans are counted with relaxations. Algorithm 1 RMQB-LRV (Randomized Multi-Quantile Bucketing with Lazy Rounds & Verification) 1: Initialize dist ( s ) = 0, dist ( v ) = ∞ for v = s ; admit s . Set r← 0 and freeze distfrz ( v ) ←dist ( v ). 2: while some bucket is nonempty do 3: B←global minimum nonempty index across all shifts 4: for all i∈[K] with bucket (i, B) nonempty do 5: while bucket (i, B) is nonempty do 6: pop a vertex vfrom (i, B) 7: if ∃(u→v) with dist(u)+w(u, v)<dist(v)then ▷verification 8: dist(v)←min(u→v)dist(u)+w(u, v);admit v 9: continue 10: Finalize v 11: for all (v→u)∈Edo 12: if dist(v) + w(v, u)<dist(u)then ▷successful relaxation 13: x←dist(u); dist(u)←dist(v)+w(v, u) 14: if dist(u)≤(1 −δ)xthen ▷significant 15: admit u 16: else if ∃i∈[K] with bi(dist(u)) < bi(distfrz(u)) then ▷minor boundary 17: admit u 18: else 19: lazy: do not re-enqueue u 20: if all shifts have empty bucket at index Bthen 21: r←r+ 1; freeze: distfrz(v)←dist(v) for all v 4 Correctness Lemma 4.1 (Monotone upper bounds).For all v and all times, dist ( v ) ≥d∗ ( v ), and labels decrease only via relaxations. Proof. Immediate from the relaxation rule and nonnegativity of weights. Lemma 4.2 (Shifted-bucket drop under significant improvement).Let x′> 0and x′≤ (1 −δ ) x . For uniform θ∈[0,1) and bθ(y) := ⌊log1+γy+θ⌋, Prθbθ(x′)< bθ(x)≥1 4. Proof. Let g ( y ) = log1+γy , a = g ( x ), a′ = g ( x′ ). Then a−a′ = log1+γ ( x/x′ ) ≥log1+γ (1 / (1 −δ )) ≥ δ/ ln (1 + γ ) ≥δ/γ = 1 / 4, using ln (1 + t ) ≤t and δ = γ/ 4. For uniform θ , the measure of {θ:⌊a′+θ⌋<⌊a+θ⌋} is at least 1/4. Remark 4.3. Lemma 4.2 is not used in the deterministic work bound; it provides intuition for why multiple shifts help. Theorem 4.4 (Exactness).RMQB-LRV returns dist(v)=d∗(v)for all v. Proof. By Lemma 4.1, labels are upper bounds. A vertex v is finalized only after checking all in-edges and finding none can improve dist ( v ). Thus no shorter s→v path can exist, and dist ( v ) = d∗ ( v ). 3 5 Work/Time Analysis We count bucket operations (logical admissions/pops/rebuckets of handles; O (1) each) and successful relaxations (strict label decreases). Let K = clog n with c a sufficiently large absolute constant. Probability is only over the random shifts; the bounds below are deterministic. 5.1 Significant improvements: deterministic potential Define g(x) = log1+γxand the potential Ψ := X vnot yet finalized K X i=1g(dist(v)) −g(d∗(v))+. A significant improvement satisfies g ( distnew ( v )) ≤g ( distold ( v )) −1 4 . Each of the K shift-terms drops by at least 1/4 (never below 0), so deterministically ∆Ψ ≤ − K/4 for every significant improvement. When v first becomes finite, g ( dist0 ( v )) −g ( d∗ ( v )) ≤O ( log U ), hence Ψ start = O ( K n log U ). Therefore the number of significant improvements is O ( nlog U ), so the number of significant admissions is also O(nlog U). Pops. Each admission of v results in at most one subsequent pop of v (the shared handle is deduplicated across shifts at the global index B), so #pops ≤#admissions + n=O(m+nlog U). 5.2 Minor improvements, intervals, and their count Define an interval for v as the time span from its most recent admission (or start) up to the next significant improvement or finalization. Lemma 5.1 (At most one minor admission per interval).Within an interval of v , at most one minor boundary admission occurs (across all shifts). Proof. On the first minor boundary crossing in any shift, the algorithm inserts v into all shifts at its new label via the shared handle. Further minor decreases in the same interval do not trigger another admission until the interval ends (by definition). Lemma 5.2 (Intervals per vertex).Let q(v)be the number of intervals of v. Then q(v)≤1 + deg−(v)+#significant(v). Proof. Each interval for v ends in exactly one way: (1) finalization (contributes the leading +1); (2) a significant drop of v (counted in # significant ( v )); or (3) advancement past v without popping v : while v remains unpopped and the global index B decreases, some predecessor u∈N− ( v ) becomes newly-effective for v (first time in the current round that bi ( dist ( u ) + w ( u, v )) < bi ( distfrz ( v )) for some shift i ). Each fixed u can become newly-effective at most once before either forcing a significant decrease of v or v being popped/finalized. Hence case (3) can end at most deg− ( v ) intervals. Summing proves the bound. 4 Lemma 5.3 (Total minor boundary admissions).The total number of admissions due to minor boundary crossings is On+X v deg−(v) + X v #significant(v)=O(m+nlog U). Proof. By Lemma 5.1, at most one per interval. Summing q ( v ) over all v and using Lemma 5.2 gives On + Pvdeg− ( v ) + Pv # significant ( v )  . Since each vertex admits O ( log U ) significant drops by geometric decrease, the total is O(m+nlog U). 5.3 Verification work On each pop of v, the verification step scans all in-edges (u→v). • If the scan finds an improving in-edge, dist ( v ) decreases. Charge the scan to that improving edge. By the geometric-scale argument below, any fixed edge can be charged at most once per scale; summing gives O(m+nlog U) charged scans. • If the scan finds no improvement, v is finalized. Each vertex contributes at most one such no-improvement scan, so these total Pvdeg−(v) = O(m) edge examinations. Therefore, verification adds O ( m + nlog U ) edge examinations overall and does not affect the bucket-operation counts. 5.4 Successful relaxations We define geometric scales at thresholds (1 + γ ) z for z∈Z . A successful relaxation of ( u→v ) is charged either (i) to the unique first decrease of v within its current scale, or (ii) to v ’s entry into the next lower scale. For a fixed scale and fixed head v , every incoming edge ( u→v ) can be charged at most once (the head’s label cannot cross the same scale boundary twice). Each v participates in O(log U) scales. Summing over all vyields: Lemma 5.4 (Relaxations).The total number of successful relaxations is O(m+nlog U). 5.5 Putting it all together Theorem 5.5 (Near-linear work).For K = clog n shifts with sufficiently large c , RMQB-LRV performs O ( m + nlog U )bucket operations and O ( m + nlog U )successful relaxations. The bound is deterministic. Proof. Significant admissions are O ( nlog U ) by the deterministic potential Ψ. Minor admissions are O ( m + nlog U ) by Lemma 5.3. Pops are at most admissions plus n , hence O ( m + nlog U ). Each admission/pop/rebucket is one logical bucket operation, so bucket operations total O ( m + nlog U ). Verification adds O ( m + nlog U ) edge examinations. Successful relaxations are O ( m + nlog U ) by Lemma 5.4. Corollary 5.6 (Sparse graphs, polynomial spread).If m = Ω( n )and U≤nO(1) , RMQB-LRV runs in ˜ O(m)time. 5 6 Discussion and Limits The algorithm is label-correcting with verification, not label-setting: a popped vertex can be reactivated if verification finds an improving in-edge. This is essential for exactness with coarse bucketing; a general label-setting variant appears to require exact global ordering or certified heuristics (A*-style), which do not yield better worst-case asymptotics in this model. Our bound depends on log U, which is standard for real-weight comparison-based SSSP. 7 Implementation Notes Buckets are arrays of vectors over a sliding window of active indices with a shared per-vertex handle; nonnegativity ensures the window advances monotonically. Each admission/pop/rebucket touches O (1) memory locations. Verification scans v ’s in-edges; each scan that lowers dist ( v ) is charged to the improving in-edge and contributes to the O(m+nlog U) relaxation bound. 8 Conclusion We presented RMQB-LRV, a simple randomized exact SSSP with near-linear work bounds in the comparison + addition model. The analysis is short and robust: (i) random multi-quantile shifts yield constant-probability bucket drops on significant improvements; (ii) a deterministic potential over shifted indices amortizes admissions; (iii) lazy admission collapses minor churn; and (iv) geometric-scale accounting bounds successful relaxations. Tightening this to truly linear time without log U, or to a label-setting algorithm in this model, remains an intriguing open direction. 6