Thorup Shortest-Paths Algorithm

The Thorup shortest-paths algorithm is a deterministic linear-time algorithm in computation and algorithms introduced by Danish computer scientist Mikkel Thorup in 1999 that solves the single-source shortest-paths (SSSP) problem on undirected graphs with positive integer edge weights in O(m + n) time and space on a standard Word RAM. Given a connected undirected graph G = (V, E) with n = |V| vertices, m = |E| edges, a source vertex s ∈ V, and a positive integer weight function ℓ : E → {1, 2, …, C} whose edge weights fit in a single machine word of w ≥ log₂ C bits, the algorithm computes the exact shortest-path distance d(s, v) and shortest-path tree parent for every vertex v ∈ V using a linear number of arithmetic, bitwise, and memory operations.

For four decades following Edsger W. Dijkstra's 1959 formulation of Dijkstra's algorithm, every known deterministic general-weight SSSP algorithm visited vertices in monotonically non-decreasing order of their true distance d(s, v) from the source. Because visiting vertices in sorted order of d(s, v) reduces integer or comparison sorting of n keys to a shortest-paths computation on a star graph, any SSSP algorithm that extracts vertices in exact distance order inherits the sorting lower bound in computational complexity theory—requiring Ω(m + n log n) comparisons in the algebraic decision-tree model, or O(m + n √(log C)) / O(m + n log log n) time using Word RAM integer priority queues built from van Emde Boas trees, fusion trees, and radix heaps. Thorup bypassed the sorting bottleneck by proving that on undirected graphs, vertices do not need to be visited in global order of d(s, v); instead, partitioning the graph iteratively by power-of-two weight thresholds 2ⁱ produces a hierarchical component tree T along which subsets of vertices can be safely finalized in bucketed batches without sorting individual distances within a bucket.

Dijkstra's Monotone Ordering and the Reduction from Sorting

Let G = (V, E) be a weighted graph with positive edge lengths ℓ(u, v) > 0 and source vertex s. Label-setting algorithms maintain a tentative distance upper bound D(v) ≥ d(v) initialized to D(s) = 0 and D(v) = +∞ for v ≠ s, together with a set S ⊆ V of visited vertices for which D(v) = d(v). When u ∈ V \ S joins S, the algorithm relaxes every incident edge (u, v) ∈ E via D(v) ← min(D(v), D(u) + ℓ(u, v)).

In Dijkstra's algorithm, correctness relies on selecting the unvisited vertex u ∈ V \ S that minimizes D(u) across the entire unvisited frontier:

Extracting the global minimum of D(x) at each of the n steps visits vertices in non-decreasing order d(u₁) ≤ d(u₂) ≤ … ≤ d(u_n). Given n arbitrary positive integers x₁, …, x_n, constructing an n-leaf star graph rooted at s with edge weights ℓ(s, v_i) = x_i forces any monotone-order SSSP algorithm to output the vertices in sorted order of x_i.

In the comparison-addition model, Michael L. Fredman and Robert E. Tarjan (1984) achieved the optimal comparison bound of O(m + n log n) using Fibonacci heaps (practically approximated by pairing heaps and binomial heaps). On a Word RAM with integer edge weights in {1, …, C}, monotone-order algorithms remained tied to integer priority queues, such as the O(m + n log C) bound of the radix heap (Ahuja, Mehlhorn, Orlin, and Tarjan 1990), the O(m + n √(log n log log n)) bound via Kirkpatrick–Reisch sort and fusion trees, and the O(m + n log log n) bound of Thorup's integer priority queues.

Why Undirected Symmetry Permits Non-Monotone Vertex Finalization

To achieve O(m + n) time independently of word length w and maximum weight C, an algorithm must avoid sorting d(v). Suppose u ∈ V \ S is not necessarily the global minimum of D(x) over V \ S, and consider any path P from s to u leaving S at some frontier vertex x ∈ V \ S. If x and u belong to different connected components of the threshold subgraph G_<Δ = (V, {e ∈ E : ℓ(e) < Δ}), then any path connecting x to u must cross at least one edge of weight ≥ Δ:

Therefore, if u minimizes D(u) within its own connected component U of G_<Δ, and if every other component U′ ≠ U of G_<Δ satisfies D(u) ≤ min_{x ∈ U′ \ S} D(x) + Δ, then no path through U′ can improve D(u), even when min_{x ∈ U′ \ S} D(x) < D(u). When distances inside each component of G_<Δ are bucketed into intervals of width Δ = 2ⁱ by the shifted quotient ⌊D(v) / Δ⌋ = D(v) ≫ i, two components U and U′ whose minimum unvisited distances fall in the same bucket [b · Δ, (b + 1)Δ − 1] differ in minimum distance by less than Δ. Because traversing between U and U′ costs at least Δ in either direction on an undirected graph, neither component can provide a shortcut into the other, and both can be finalized independently without sorting their distances inside bucket b.

Power-of-Two Threshold Subgraphs G_i

Let the edge weights be positive w-bit integers ℓ(e) ∈ {1, 2, …, 2^w − 1}. For each integer bit scale i ∈ {0, 1, …, w}, define the level-i threshold subgraph:

At scale i = 0, the edge set E₀ is empty because ℓ(e) ≥ 1 = 2⁰, so the connected components of G₀ are the n singleton vertices {v}. At scale i = w, every edge satisfies ℓ(e) < 2^w, so G_w = G is a single connected component V. For 0 < i < w, every connected component of G_i−1 is a subset of a unique connected component of G_i because E_i−1 ⊆ E_i.

This nested refinement defines a rooted component hierarchy (component tree) T of height at most w:

1. Nodes of T: A node at level i is a pair ([v]_i, i), where [v]_i ⊆ V is the connected component of G_i containing vertex v.
2. Leaves and Root: The leaves are the n singleton components ({v}, 0) at level i = 0, and the root is the global component (V, w) at level i = w.
3. Parent–Child Relation and Unary Contraction: The children of (X, i) in T are the connected components (Y₁, i − 1), …, (Y_k, i − 1) of G_i−1 that partition X. To bound the tree size by |T| < 2n (linear O(n) space rather than O(n · w)), Thorup contracts every unary chain where [v]_i = [v]_i−1 so that every internal node in T has at least two children.

Component Distance Bounds and Safe Visiting Criteria

For any node X = ([v]_i, i) in T, let X⁻ = X \ S denote the unvisited vertices in X, and define:

A component node (X, i) is called minimal if min-D(X) = min-d(X). The root (V, w) is invariantly minimal throughout execution because the global minimum of D(v) over V \ S always equals min-d(V). At a leaf ({v}, 0), minimality means D(v) = d(v), certifying that v can be added to S and its incident edges relaxed.

Inductively, suppose a parent component (X, i) is minimal, and let (Y, i − 1) be a child of (X, i) in T (separated from all sibling children Y′ ⊂ X by edges of weight ≥ 2ⁱ⁻¹). If (Y, i − 1) minimizes the shifted distance bucket among all active children of (X, i):

then for every sibling Y′ ≠ Y, min-D(Y′) + 2ⁱ⁻¹ > min-D(Y). Thus no path through any unvisited vertex outside Y⁻ can achieve a distance smaller than min-D(Y), proving that (Y, i − 1) is also minimal: min-D(Y) = min-d(Y).

Bounding the Bucket Array Range per Component

Suppose component (X, i) consists of |X| vertices connected in G_i by edges of weight < 2ⁱ. Because a spanning tree of X in G_i has |X| − 1 edges of length < 2ⁱ, the diameter of X in G satisfies max_{u,v ∈ X} |d(u) − d(v)| ≤ (|X| − 1) · 2ⁱ. More tightly, if X decomposes into k children Y₁, …, Y_k at level i − 1, the internal diameter across those k child components at scale 2ⁱ⁻¹ spans at most 2k buckets from the first bucket b_min(X) = min-D(X) ≫ (i − 1) to the last bucket b_max(X).

Rather than allocating an array indexed up to 2^w, each component (X, i) allocates a local contiguous bucket array B(X)[b_min .. b_max] of length proportional to the number of child subcomponents. Summing bucket array lengths over all internal nodes of T telescopes to O(m + n) total buckets and O(m + n) bucket-pointer increments.

The Recursive Visit(X, i) Procedure

With the component hierarchy T and local bucket arrays B(X) initialized, Thorup's traversal executes a depth-first bucket scan over T:

1. Base Case (i = 0, Leaf X = {v}): When Visit({v}, 0) is called on a minimal leaf, D(v) = d(v) is exact. Add v to S, and for every incident edge (v, u) ∈ E with u ∉ S, relax D(u) ← min(D(u), d(v) + ℓ(v, u)), updating the bucket position of the lowest active ancestor component of u if D(u) decreases.
2. Inductive Case (i > 0, Internal Node (X, i)): Let b = ix(X) = min-D(X) ≫ (i − 1) be the current active bucket index of minimal component (X, i). While bucket B(X)[b] is non-empty:
   • Select any child component (Y, i − 1) in B(X)[b] (which is guaranteed to be minimal) and recursively call Visit(Y, i − 1) to finalize all vertices v ∈ Y⁻ with d(v) ≫ (i − 1) = b.
   • After Visit(Y, i − 1) returns, all remaining vertices in Y⁻ satisfy min-D(Y) ≫ (i − 1) > b. Remove Y if Y⁻ = ∅, or move Y forward to bucket B(X)[min-D(Y) ≫ (i − 1)].
3. Advancing the Bucket Pointer: Once B(X)[b] is empty, increment ix(X) ← ix(X) + 1 until reaching the next non-empty bucket or until min-D(X) ≫ i increases (returning control to the parent of X).

Minimum Spanning Tree Reduction and Tree Union-Find

Naively building G₀, …, G_w would take O(m · w) time. Thorup constructs the compressed component tree T in O(m + n) time via three reductions:

1. Minimum Spanning Tree Restriction: Two vertices u and v lie in the same connected component of G_i if and only if the unique path between u and v in a minimum spanning tree M of G uses only edges of weight < 2ⁱ. While Kruskal's algorithm sorts all m edges, Fredman and Willard (1994) proved that a minimum spanning tree M can be computed deterministically in linear O(m + n) time on a Word RAM using atomic heaps (Q-heaps).
2. Most-Significant-Bit Scale Labelling: For each of the n − 1 edges e ∈ M, its threshold scale i = ⌊log₂ ℓ(e)⌋ + 1 is computed in O(1) Word RAM operations via fusion-tree multiplication or hardware leading-zero count.
3. Linear-Time Tree Disjoint-Set Union: Merging the n − 1 edges of M across active scales uses Harold N. Gabow and Robert E. Tarjan's (1985) linear-time special-case disjoint-set data structure on static trees in O(n) time.

Similarly, to avoid walking up Θ(w) ancestor levels in T on every edge relaxation, unvisited subtrees of T below the lowest expanded ancestor are maintained as contracted sets in a second Gabow–Tarjan tree union-find structure, ensuring O(1) amortized work per edge relaxation and O(m + n) total worst-case time.

Why Directed Graphs Resist O(m + n) Component Bucketing

In a directed graph G = (V, E), edge weights are asymmetric: the arc (u, v) may have weight ℓ(u, v) = 1 while the reverse arc (v, u) has weight +∞. In a strongly connected component X of a directed threshold subgraph G_i, a path from u to v may use a single edge of weight < 2ⁱ, whereas the shortest return path from v to u inside X must traverse up to |X| − 1 edges; worse, vertices linked by a one-way arc cannot be grouped into a symmetric component of bounded diameter. Torben Hagerup (2000) generalized Thorup's component-tree approach to directed graphs with positive integer weights in O(m + n log w) = O(m + n log log C) time by resolving strongly connected threshold components and binary-searching over active bucket intervals. Whether deterministic O(m + n) SSSP is achievable on directed graphs remains open.

Real-Weight Adaptation and the Pettie–Ramachandran Bound

Seth Pettie and Vijaya Ramachandran (2005) adapted the component-tree framework to the comparison-addition model for undirected graphs with arbitrary positive real edge weights (where bitwise shifts D(v) ≫ i are unavailable), achieving O(m α(m, n) + min(n log n, n log log r)) time where r = max_e ℓ(e) / min_e ℓ(e) is the maximum-to-minimum weight ratio.

How does Thorup's algorithm beat the Ω(n log n) sorting lower bound?

The Ω(n log n) lower bound applies to comparison-addition algorithms and to SSSP algorithms required to output vertices in sorted order of their distance d(s, v). Thorup's algorithm uses Word RAM bitwise right-shifts D(v) ≫ i to bucket distances by powers of two in O(1) time and does not sort the vertices by distance; it outputs exact distances d(s, v) and the shortest-path tree while finalizing vertices in bucketed component batches whose internal distances are unordered.

Does Thorup's algorithm work on graphs with zero-weight or negative-weight edges?

Zero-weight edges (ℓ(e) = 0) are handled in O(m + n) preprocessing time by contracting every connected component of the zero-weight subgraph into a single super-vertex before building T. Negative-weight edges (ℓ(e) < 0) are incompatible because any undirected edge with ℓ(u, v) < 0 forms a negative-weight 2-cycle u → v → u, making shortest simple paths NP-hard.

Why is Dijkstra's algorithm with binary or pairing heaps still preferred in many software libraries?

Although Thorup's algorithm is asymptotically optimal at O(m + n), its implementation requires Fredman–Willard atomic heaps, a compressed component hierarchy T, Gabow–Tarjan tree union-find structures, and dynamic bucket arrays at every internal node of T. The constant factor involves multiple pointer indirections and cache misses per vertex, whereas a cache-friendly binary heap, pairing heap, or radix heap scans contiguous arrays inside L1/L2 processor caches.

Can the component hierarchy T be reused for multiple source vertices?

Yes. Because the threshold subgraphs G_i and the compressed component hierarchy T depend only on the minimum spanning tree of G and the edge weights ℓ(e) rather than the source vertex s, T can be built once in O(m + n) preprocessing time and reused across shortest-path queries from arbitrary sources s₁, …, s_k.

1. Thorup, M. (1999). "Undirected single-source shortest paths with positive integer weights in linear time." Journal of the ACM, 46(3), 362–394.
2. Fredman, M. L., & Willard, D. E. (1994). "Trans-dichotomous algorithms for minimum spanning trees and shortest paths."80064-9) Journal of Computer and System Sciences, 48(3), 533–551.
3. Gabow, H. N., & Tarjan, R. E. (1985). "A linear-time algorithm for a special case of disjoint set union."90014-5) Journal of Computer and System Sciences, 30(2), 209–221.
4. Hagerup, T. (2000). "Improved shortest paths on the word RAM." In Automata, Languages and Programming (ICALP 2000), Lecture Notes in Computer Science, vol. 1853 (pp. 61–72). Springer.
5. Pettie, S., & Ramachandran, V. (2005). "A shortest path algorithm for real-weighted undirected graphs." SIAM Journal on Computing, 34(6), 1398–1431.