Overview
Lifelong Dijkstra is a incremental search method for dynamic shortest paths. It works by reusing previous shortest-path information after edge cost changes.
ExtendedSource checked
Lifelong Dijkstra
Lifelong Dijkstra addresses dynamic shortest paths by reusing previous shortest-path information after edge cost changes.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Incremental Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dynamic shortest pathsincremental searchpathfinding
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use Lifelong Dijkstra when solving dynamic shortest paths and you want to benefit from reusing previous shortest-path information after edge cost changes.
- Choose it when O(n) average/worst-case time and O(1) memory match your workload profile.
- Prefer it over Visibility Graph Roadmap or 0-1 BFS when the problem structure favors dynamic shortest paths.
When Not to Use
- Avoid when path costs or obstacles change in ways the method cannot update efficiently.
- Avoid when approximate paths are unacceptable and the method does not guarantee optimality.
What It Does
- Computes dynamic shortest paths within Incremental Search workloads (O(n) time, O(1) space).
- Works by reusing previous shortest-path information after edge cost changes.
- Maintains key invariants across dynamic shortest paths, incremental search, pathfinding.
Use Cases
- Production and research workloads requiring dynamic shortest paths via reusing previous shortest-path information after edge cost changes.
- Incremental Search pipelines where O(n) time and O(1) space fit system constraints.
- Engineering comparisons against Visibility Graph Roadmap and 0-1 BFS when tuning dynamic shortest paths.
Inputs
- Incremental Search input instance for dynamic shortest paths
- Configuration parameters controlling dynamic shortest paths
Outputs
- Computed dynamic shortest paths solution produced by Lifelong Dijkstra
- Diagnostic state over dynamic shortest paths and incremental search
Pseudocode
- 1.Initialize the search space, start/goal states, and cost/priority tables for Lifelong Dijkstra.
- 2.Insert the initial state into the open frontier or roadmap with its baseline cost and heuristic estimate.
- 3.Expand or sample candidate transitions by reusing previous shortest-path information after edge cost changes.
- 4.Update path costs, parent pointers, or conflict constraints whenever an improved trajectory is found.
- 5.Reconstruct and return the collision-free path from start to goal once the termination criterion holds.
Canonical Example
- Input
- Incremental Search input instance for dynamic shortest paths configured for a representative dynamic shortest paths test case
- Output
- Computed dynamic shortest paths solution produced by Lifelong Dijkstra satisfying Lifelong Dijkstra invariants
- Explanation
- Lifelong Dijkstra processes the input by reusing previous shortest-path information after edge cost changes, tracking dynamic shortest paths and incremental search to produce the verified dynamic shortest paths result.
Implementation Notes
- Separate search state from world state so changes can be tested.
- Use small maps with known optimal answers before large scenarios.
- Track whether returned paths are optimal, bounded, or heuristic.
Common Pitfalls
- Using an inadmissible heuristic where optimality is expected.
- Ignoring dynamic obstacles, time-dependent costs, or changing edge weights.
- Testing only open grids and missing narrow-passage cases.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow reusing previous shortest-path information after edge cost changes on a small dynamic shortest paths example.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Initialize the search space, start/goal states, and cost/priority tables for Lifelong Dijkstra.
pathfinding-mechanismNotes
Lifelong Dijkstra operates in O(n) time and O(1) space within the Incremental Search family. Often compared with Visibility Graph Roadmap and 0-1 BFS.
Sources (2)
What each reference supports for this entry.
Lifelong Planning A*
PaperReference for incremental shortest-path replanning with g and rhs values.
Open sourceIntroduction to Algorithms (CLRS)
BookAlgorithms textbook support for Lifelong Dijkstra invariants, search ordering, correctness argument, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborLifelong Planning A*
Both maintain shortest-path information across graph changes; LPA* adds A*-style heuristic guidance.
Tags
PathfindingGraph