Pathfinding
Algorithms that find routes through graphs or spaces.
Pathfinding algorithms choose paths between points while considering distance, cost, constraints, or estimates of future cost.
Dijkstra's Algorithm
Finds shortest paths from one source in a graph with nonnegative edge weights.
A* Search
Finds a low-cost path by combining path cost so far with a heuristic estimate to the goal.
Bellman-Ford
Finds single-source shortest paths even when edges can have negative weights.
Floyd-Warshall
Finds shortest paths between every pair of nodes.
Greedy Best-First Search
Expands the node that appears closest to the goal by heuristic estimate.
Hierarchical Pathfinding
Speeds pathfinding by planning through coarse regions before refining locally.
Johnson's Algorithm
Finds all-pairs shortest paths in sparse graphs by reweighting edges.
Jump Point Search
Speeds up grid pathfinding by skipping over symmetric intermediate nodes.
Lee Algorithm
Finds shortest paths on a grid by expanding wavefront distances.
Yen's K Shortest Paths
Finds several shortest loopless paths between the same two nodes.
Acyclic Shortest Path
Finds shortest paths in a weighted DAG by relaxing edges in topological order.
Flow Field Pathfinding
Guides many agents toward a goal by precomputing a direction field over a grid.
Theta*
Finds smoother grid paths by allowing line-of-sight shortcuts during A* search.
D* Lite
Repairs shortest paths efficiently when edge costs change during navigation.
Bidirectional Dijkstra
Finds a shortest path by running Dijkstra search forward from the start and backward from the goal.
Fringe Search
Searches with A*-style costs while batching nodes by a moving cost threshold.
IDA*
Combines A* scoring with iterative deepening to search with lower memory use.
Lifelong Planning A*
Reuses previous A* search work when graph costs change.
D* Search
Repairs paths for a moving agent as new obstacle or cost information appears.
Contraction Hierarchies
Speeds shortest-path queries by contracting less important nodes and adding shortcut edges.
ALT Landmarks
Uses landmark distances and triangle inequalities to guide shortest-path search.
Multi-Source Dijkstra
Finds shortest distances from the nearest of several source nodes in a nonnegative-weight graph.
Anytime Repairing A*
Quickly finds a usable path and improves it as more time is available.
Rapidly-Exploring Random Tree
Builds a tree of random feasible motions that quickly explores open space.
Weighted A*
Weighted A* finds routes through graphs, grids, or motion-planning spaces.
Lazy Theta*
Lazy Theta* guides route search with a heuristic score.
Anya Pathfinding
Anya Pathfinding finds routes through graphs, grids, or motion-planning spaces.
Block A*
Block A* finds routes through graphs, grids, or motion-planning spaces.
Subgoal Graph Pathfinding
Subgoal Graph Pathfinding finds routes through graphs, grids, or motion-planning spaces.
HPA*
HPA* finds routes through graphs, grids, or motion-planning spaces.
Incremental Dijkstra
Incremental Dijkstra updates paths efficiently as graph costs change.
Multi-Heuristic A*
Multi-Heuristic A* finds routes through graphs, grids, or motion-planning spaces.
Real-Time Adaptive A*
Real-Time Adaptive A* finds routes through graphs, grids, or motion-planning spaces.
Probabilistic Roadmap
Probabilistic Roadmap samples feasible states and connects them into paths.
RRT*
RRT* addresses motion planning by rewiring a rapidly-exploring random tree to improve path cost over time.
Visibility Graph Roadmap
Visibility Graph Roadmap handles shortest path among obstacles by connecting mutually visible obstacle vertices and searching the resulting graph.
0-1 BFS
Finds shortest paths in graphs whose edge weights are only 0 or 1.
Dial's Algorithm
Dial's Algorithm addresses shortest paths with small integer weights by using buckets instead of a heap for bounded nonnegative edge weights.
Eppstein K Shortest Paths
Eppstein K Shortest Paths addresses k shortest paths by building a sidetrack structure that enumerates paths after one shortest-path tree.
LRTA*
LRTA* addresses online pathfinding by updating heuristic estimates while acting one step at a time.
Conflict-Based Search
Conflict-Based Search addresses multi-agent pathfinding by splitting conflicts into constraints and solving constrained paths for each agent.
Safe Interval Path Planning
Safe Interval Path Planning addresses dynamic obstacle pathfinding by searching intervals when each state is safely traversable.
Lazy PRM
Lazy PRM addresses motion planning by building a probabilistic roadmap while deferring expensive collision checks.
RRT-Connect
RRT-Connect addresses motion planning by growing two random trees toward each other until they connect.
Anytime D*
Anytime D* addresses dynamic pathfinding by refining a repairable path while gradually tightening the heuristic bound.
Lifelong Dijkstra
Lifelong Dijkstra addresses dynamic shortest paths by reusing previous shortest-path information after edge cost changes.
Multi-Goal A*
Multi-Goal A* addresses multi-target pathfinding by searching toward the best among several goals using admissible goal estimates.
Dynamic Window Approach
Chooses robot velocity commands by simulating short feasible motions and scoring them.