Overview
ALT preprocesses distances to selected landmarks, then turns those values into admissible A* heuristics for faster route queries.
ExtendedSource checked
ALT Landmarks
Uses landmark distances and triangle inequalities to guide shortest-path search.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Advanced
- Family
- Heuristic Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- A* Landmarks Triangle inequality
Core Concepts
landmark distancetriangle inequalityadmissible heuristicroute preprocessing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E log V)
Average
O(E log V)
Worst
O(E log V)
Space
O(k V)
When to Use
- Use when route planning needs landmark distance.
- Use when the input matches the assumptions behind heuristic Search.
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
- Uses landmark distances and triangle inequalities to guide shortest-path search
- Uses landmark distance and triangle inequality 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)
ALT heuristic
h(v, t) = maxl |dist(l, t) − dist(l, v)|
h(v, t) = max_l |dist(l, t) - dist(l, v)|Uses landmark distances to lower-bound the remaining distance.
Pseudocode
- 1.Prepare the inputs and state needed for ALT Landmarks.
- 2.Apply the landmark distance step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return path.
Canonical Example
- Input
- ALT Landmarks input with a small representative case
- Output
- Path
- Explanation
- ALT Landmarks applies landmark distance to produce path.
Implementation Notes
- Store predecessor information separately from distance or priority values.
- Keep the landmark distance 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 ALT Landmarks 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 ALT Landmarks.
pathfinding-mechanismNotes
ALT Landmarks should be used with the assumptions and tradeoffs of heuristic Search in mind.
Sources (1)
What each reference supports for this entry.
ALT Landmarks
PaperReference for A*, landmarks, and triangle-inequality lower bounds in road-network routing.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageImproves onA* Search
ALT uses landmark distances to strengthen A* heuristics.
Alternative toContraction Hierarchies
Both use preprocessing to accelerate route planning.
Related Algorithms
Tags
PathfindingHeuristic SearchShortest PathPreprocessing