Overview
Contraction hierarchies preprocess a road-like graph into levels so queries can search mostly upward through shortcut edges instead of exploring the full graph.
SpecializedSource checked
Contraction Hierarchies
Speeds shortest-path queries by contracting less important nodes and adding shortcut edges.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Advanced
- Family
- Route Planning
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
shortcut edgenode orderingbidirectional queryroute preprocessing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log V)
Average
O(log V)
Worst
O(E log V)
Space
O(V + E)
When to Use
- Use when route planning needs shortcut edge.
- Use when the input matches the assumptions behind route Planning.
When Not to Use
- Avoid when edge costs or movement rules change faster than the search can update them.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Speeds shortest-path queries by contracting less important nodes and adding shortcut edges
- Uses shortcut edge and node ordering to guide the work.
- Produces path.
Use Cases
- Route planning
- Game navigation
- Robotics motion planning
Inputs
- Search graph or state space
- Start state
- Goal state or target set
Outputs
- Path
- Distance estimate
- Search frontier state
Key Formulas (1)
Shortcut condition
shortcut(u, w) needed if distwithout v(u, w) > cost(u, v) + cost(v, w)
shortcut(u, w) needed if dist_without_v(u, w) > cost(u, v) + cost(v, w)Adds a shortcut when removing v would otherwise hide a shortest path.
Pseudocode
- 1.Prepare the inputs and state needed for Contraction Hierarchies.
- 2.Apply the shortcut edge step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return path.
Canonical Example
- Input
- Contraction Hierarchies input with a small representative case
- Output
- Path
- Explanation
- Contraction Hierarchies applies shortcut edge to produce path.
Implementation Notes
- Store predecessor information separately from distance or priority values.
- Keep the shortcut edge step separate enough to test independently.
Common Pitfalls
- Using a heuristic or preprocessed data that does not match the actual cost model breaks path quality.
- Forgetting to check edge cases can make Contraction Hierarchies look correct on only ideal inputs.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier, settled nodes, and the final path over the search space.
S
#
#
#
#
#
#
#
G
Step 1 of 4: Prepare the inputs and state needed for Contraction Hierarchies.
pathfinding-mechanismNotes
Contraction Hierarchies should be used with the assumptions and tradeoffs of route Planning in mind.
Sources (1)
What each reference supports for this entry.
Contraction Hierarchies
PaperReference for node contraction and shortcut-based road-network shortest paths.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborALT Landmarks
Both speed up shortest-path queries through preprocessing.
Improves onDijkstra's Algorithm
Contraction hierarchies preprocess shortcuts to accelerate shortest-path queries.
Related Algorithms
Tags
PathfindingShortest PathPreprocessingWeighted Graph