Pathfinding Algorithms
Master 8 pathfinding algorithms with side-by-side comparisons. Understand when to use each one, explore real-world applications, and prepare for technical interviews.
What Is Pathfinding? (More Than Just Mazes)
Pathfinding is the process of finding a route from one point to another while navigating constraints. Those constraints might include:
- Distance
- Cost
- Obstacles
- Time
- Risk
- Memory limits
At its core, pathfinding is about decision making under uncertainty. Every step answers the same question:
Where should I go next to get closer to my goal?
Pathfinding algorithms are not just about maps. They are about exploring possibilities efficiently.
Mental model: Pathfinding is like navigating a new city without GPS. You explore, backtrack, remember dead ends, and eventually find your way. Different strategies work better depending on how much you know about the terrain.
Where Pathfinding Actually Matters
Pathfinding powers systems people use every day.
Navigation & Maps
- GPS route planning
- Traffic-aware rerouting
- Walking, driving, cycling paths
Games & Simulations
- NPC movement
- Enemy pursuit logic
- Strategy and resource planning
Robotics
- Obstacle avoidance
- Warehouse robots
- Autonomous vehicles
Logistics & Networks
- Packet routing on the internet
- Shortest routes for pick-and-pack
- Robot fleet coordination
Key idea: Pathfinding is everywhere decisions involve moving through a space efficiently.
Complexity Comparison
| Algorithm | Time | Space | Shortest? | Data Structure |
|---|---|---|---|---|
| Breadth-First Search | O(V + E) | O(V) | Queue (FIFO) | |
| Depth-First Search | O(V + E) | O(V) (often O(depth)) | Stack (LIFO) or Recursion | |
| Dijkstra's Algorithm | O((V + E) log V) | O(V) | Priority Queue (Min-Heap) | |
| A* Search | O((V + E) log V) | O(V) | Priority Queue (ordered by f-score) | |
| Greedy Best-First Search | O((V + E) log V) | O(V) | Priority Queue (ordered by h-score) | |
| Bidirectional A* | O(b^(d/2)) | O(V) | Two Priority Queues | |
| Flood Fill | O(V + E) | O(V) | Queue or Stack | |
| Random Walk | O(∞) / O(Luck) | O(1) | None (RNG) |
Click any algorithm name to read its full article with code examples, history, and use cases.
Why Different Problems Need Different Algorithms
Pathfinding algorithms optimize for different things. Some guarantee the shortest path. Some explore faster but may miss the best solution. Some use more memory. Some trade accuracy for speed.
| Scenario | Good Choice |
|---|---|
| Unweighted grid | BFS |
| Weighted graph | Dijkstra |
| Large search space | A* |
| Limited memory | DFS |
| Fast approximation | Greedy |
| Unknown environment | Random Walk |
Engineering truth: The “best” algorithm depends on what you can afford to trade.
How Algorithms Decide Where to Go Next
Most pathfinding algorithms revolve around three ideas:
Frontier
The set of places we can go next
Visited Set
Where we have already been
Priority
Which option looks most promising
Different algorithms change how the frontier is ordered:
- BFS explores evenly (first-in, first-out)
- DFS dives deep (last-in, first-out)
- Dijkstra prioritizes lowest cost so far
- A* balances cost and heuristic guess
Same ingredients. Different strategy.
Quick Decision Guide
Need guaranteed shortest path?
Working with unweighted grids?
Graph has weighted edges?
Memory is very limited?
Need to explore entire space?
Unknown terrain or learning algorithms?
Common Interview Questions
Why does BFS guarantee the shortest path?
Because it explores level by level. The first time it reaches the target is the shortest path in an unweighted graph.
When should you not use DFS for pathfinding?
When you need the shortest path or when the graph is very deep. DFS can wander far before finding a solution.
Follow-up: DFS is great when memory is tight or when any path will do.
Why is Dijkstra slower than BFS?
Because it handles weights and uses a priority queue. Extra flexibility comes with extra cost.
What makes A* faster than Dijkstra?
A* uses a heuristic to guide the search toward the goal instead of expanding evenly. A good heuristic dramatically reduces explored nodes.
Can A* be incorrect?
Yes. If the heuristic overestimates, A* can miss the shortest path. The heuristic must be admissible (never overestimate) to guarantee optimality.
Myths and Quick Facts
Pathfinding Myths
"DFS is always bad"
It is great when memory is tight
"A* is always best"
Only with a good heuristic
"Shortest path is always required"
Sometimes fast and good-enough wins
"Random Walk is useless"
Great teaching tool for exploration vs exploitation
Did You Know?
- Many AI systems combine multiple pathfinding strategies
- Heuristics are educated guesses, not magic
- Pathfinding problems scale exponentially
- Most real systems accept approximate paths
Algorithm Personalities
BFS is careful and methodical. DFS is adventurous and reckless. Dijkstra is precise and expensive. A* is smart when given good hints. Random Walk has no plan and vibes only.
See Pathfinding in Action
Draw walls, move the start and end points, and watch how different algorithms explore the space. Some rush forward. Some carefully evaluate every option. Some get lost. Understanding these behaviors visually builds intuition that textbooks cannot.
Open Pathfinding Visualizer