Pathfinding (Graph Search)
The quiet mathematics behind Google Maps, game characters, and logistics.
Pathfinding Algorithms
Imagine you're in an unfamiliar city looking for the train station. Different search strategies exist:
Uninformed search (like BFS or Dijkstra): Systematically explores all streets without knowing where the station is. Thorough, but time-consuming. Informed search (like A* or Greedy): Uses a 'compass' - estimates the direction to the goal and prioritizes paths leading that way.
The right choice of algorithm depends on your situation: Do you need the shortest path? How much do you know about the goal's location?
Analogy:
Imagine you're in an unfamiliar city looking for the train station. Different search strategies exist:
Uninformed search (like BFS or Dijkstra): Systematically explores all streets without knowing where the station is. Thorough, but time-consuming. Informed search (like A* or Greedy): Uses a 'compass' - estimates the direction to the goal and prioritizes paths leading that way.
The right choice of algorithm depends on your situation: Do you need the shortest path? How much do you know about the goal's location?
Definition:
Pathfinding algorithms search for routes through a graph from a start node to a goal node. They differ in how they prioritize which nodes to explore next: some guarantee the shortest path (optimal), others are faster but may find suboptimal routes. The algorithms below demonstrate these different strategies.
How This Demo Works
This demo shows how different pathfinding algorithms work. You can watch the algorithm in action and see how it finds the path step by step.
Interacting with the Demo
Draw walls on the grid to create obstacles. Set start and goal points. Choose an algorithm and click 'Start' to watch the search unfold.
What the Colors Mean
Yellow cells are in the Open List (waiting to be explored). Blue cells have already been visited (Closed List). The green path shows the found route.
The Different Algorithms
Each algorithm searches differently: A* uses a heuristic for direction, Dijkstra searches evenly in all directions, and Greedy runs straight toward the goal. Compare them to see their strengths and weaknesses.
Interactive Pathfinding Demo
What happens on the grid
This demo searches for the shortest path across a grid. Here is what you see on screen — the numbers below the grid keep count of it all.
- What you see
- A grid of tiles with a start (🤖), a goal (🚩) and black walls in between. Around the start lies a patch of coloured cells that reaches around the walls.
- What happens
- From the start, a front of visited cells grows outward and flows around the walls — like spreading water. The moment it reaches the goal, the shortest path lights up as one connected line from start to goal.
- What you can do
- Draw walls or move the start and goal, pick an algorithm, then run the search or step through it one move at a time. The speed control sets how fast the front spreads.
- What to watch for
- The search does not flail blindly in every direction. Some methods head straight for the goal, others spread out evenly — and either way the shortest path is found, guaranteed.
Named after Manhattan's rectangular street grid: You can only move horizontally or vertically, never diagonally. The distance is the sum of steps in X and Y direction.
Choose a scenario to observe different algorithm behaviors:
How A* Works
The A* Search Algorithm
A* (pronounced 'A-star') is one of the most popular pathfinding algorithms. It was developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael. A* combines the best of Dijkstra's algorithm (guaranteed shortest path) with Greedy Best-First Search (fast directional search).
The key insight of A* is the formula f(n) = g(n) + h(n), where g(n) is the actual cost from start to current node, and h(n) is the estimated cost from current node to goal (the heuristic). By always expanding the node with lowest f-value, A* efficiently finds the optimal path.
The Heuristic Function
The heuristic h(n) is an estimate of the remaining distance. Common heuristics include: Manhattan distance (sum of horizontal and vertical distances), Euclidean distance (straight-line distance), and Chebyshev distance (maximum of horizontal and vertical distances).
For A* to guarantee the optimal path, the heuristic must be admissible - it must never overestimate the actual cost. An optimistic heuristic ensures we never miss a better path.
Advantages of A*
- Optimal: Guarantees the shortest path when using an admissible heuristic
- Efficient: Explores fewer nodes than Dijkstra by using directional guidance
- Flexible: Works with different heuristics for various scenarios
- Complete: Will find a path if one exists
Practical Applications
A* is used everywhere: video game pathfinding, GPS navigation, robotics, network routing, puzzle solving (like the 15-puzzle), and AI planning. Its efficiency and optimality make it the go-to algorithm for pathfinding problems.
Try the demo! Watch how A* uses the heuristic to find the shortest path efficiently. Compare it with Dijkstra to see the difference!
1
# A* Pathfinding Algorithm
2
function a_star(start, goal, grid):
3
# Find shortest path using heuristic guidance
4
open_list = PriorityQueue() # Nodes to explore
5
closed_list = Set() # Already explored
6
open_list.add(start, f=0)
7
8
while open_list is not empty:
9
# Select node with lowest f-value
10
current = open_list.pop_lowest_f()
11
open_list.remove(current)
12
closed_list.add(current)
13
14
# Check if we reached the goal
15
if current == goal:
16
path = reconstruct_path(current)
17
return path # Success!
18
19
# Explore all neighbors
20
for each neighbor of current:
21
if neighbor in closed_list:
22
continue # Skip already explored
23
24
# Calculate tentative g score
25
tentative_g = current.g + distance(current, neighbor)
26
27
if neighbor not in open_list:
28
open_list.add(neighbor)
29
else if tentative_g < neighbor.g:
30
# Found a better path!
31
32
# Update neighbor values
33
neighbor.g = tentative_g
34
neighbor.h = heuristic(neighbor, goal)
35
neighbor.f = neighbor.g + neighbor.h
36
neighbor.parent = current
37
38
return null # No path found
🚀 Initialize Lists
Create the Open List (nodes to explore) and Closed List (already explored). Add the start node to the Open List with f=0.
open_list = PriorityQueue() # Nodes to explore
closed_list = Set() # Already explored
open_list.add(start, f=0)
🏁 Start
Initialize Open and Closed lists. Add start node with g=0, h=heuristic to goal.
📊 Select Node
Pop node with lowest f-value. Move from Open to Closed list.
🎯 Goal Check
Is this the goal? If yes, reconstruct path. If no, continue exploring.
🔀 Expand
Get all walkable neighbors. Skip those in Closed list.
🧮 Evaluate
Calculate f = g + h for each neighbor. Update if better path found.
How Dijkstra Works
Dijkstra's Algorithm
Dijkstra's algorithm, invented by Edsger Dijkstra in 1956, finds the shortest path from a start node to all other nodes in a graph. Unlike A*, it doesn't use any heuristic - it explores systematically in all directions.
The algorithm maintains a distance value for each node. Starting from 0 at the start node, it always expands the node with the smallest known distance. This guarantees finding the optimal path.
How it Works
Dijkstra expands in a circular pattern from the start, like ripples on water. It visits nodes in order of their distance from start, ensuring the shortest path is found when the goal is reached.
Properties
- Optimal: Always finds the shortest path
- Complete: Will find a path if one exists
- No Heuristic: Doesn't know goal direction
- More Exploration: Often visits more nodes than A*
Watch the demo! See how Dijkstra explores in all directions - compare with A* to see the difference!
1
# Dijkstra's Shortest Path Algorithm
2
function dijkstra(start, goal, graph):
3
# Find shortest path without heuristic
4
open_list = PriorityQueue() # To explore
5
closed_list = Set() # Explored
6
start.distance = 0
7
open_list.add(start)
8
9
while open_list not empty:
10
# Select node with smallest distance
11
current = open_list.get_min_distance()
12
open_list.remove(current)
13
closed_list.add(current)
14
15
# Check if goal reached
16
if current == goal:
17
path = reconstruct_path(current)
18
return path # Found!
19
20
# Explore all neighbors
21
for each neighbor of current:
22
if neighbor in closed_list:
23
continue # Skip explored
24
25
# Calculate new distance
26
new_dist = current.distance + edge_cost
27
if new_dist < neighbor.distance:
28
neighbor.distance = new_dist
29
neighbor.parent = current
30
if neighbor not in open_list:
31
open_list.add(neighbor)
32
33
return null # No path found
🚀 Initialize
Create open list (priority queue) and closed list. Set start node distance to 0, all others to infinity. Add start to open list.
open_list = PriorityQueue() # To explore
closed_list = Set() # Explored
start.distance = 0
open_list.add(start)
🏁 Start
Initialize distances. Start = 0, others = infinity.
📊 Select
Get node with minimum distance from open list.
🎯 Check
Is this the goal? Yes = done! No = continue.
🔀 Expand
Get all neighbors. Skip already explored.
🧮 Update
Calculate new distances. Update if shorter.
How Greedy Best-First Works
Greedy Best-First Search
Greedy Best-First Search always moves toward the goal as directly as possible. It only considers the heuristic h(n) - the estimated distance to the goal - ignoring how far it has already traveled.
This makes it very fast when there are no obstacles, but it can get trapped in dead ends because it doesn't consider the actual path cost.
The Greedy Approach
Like someone walking toward a mountain - always heading in its direction without considering if there's a cliff in the way. Fast when the path is clear, problematic when obstacles exist.
Properties
- Fast: Goes directly toward goal
- Not Optimal: May not find shortest path
- Can Get Stuck: Traps fool it easily
- Low Memory: Explores fewer nodes
Try the spiral scenario! Watch how Greedy walks into the trap while A* finds the way around.
1
# Greedy Best-First Search
2
function greedy_search(start, goal):
3
# Always follow the heuristic
4
open_list = PriorityQueue() # By h value
5
closed_list = Set() # Explored
6
open_list.add(start)
7
8
while open_list not empty:
9
# Select node closest to goal (h)
10
current = open_list.get_min_h()
11
open_list.remove(current)
12
closed_list.add(current)
13
14
# Check if goal reached
15
if current == goal:
16
path = reconstruct_path(current)
17
return path # Found!
18
19
# Explore neighbors
20
for each neighbor of current:
21
if neighbor in closed_list:
22
continue # Skip explored
23
24
# Only calculate heuristic
25
neighbor.h = heuristic(neighbor, goal)
26
neighbor.parent = current
27
if neighbor not in open_list:
28
open_list.add(neighbor)
29
30
return null # No path found
🚀 Initialize
Create open list and closed list. Add start node to open list. No distance tracking needed - only heuristic matters.
open_list = PriorityQueue() # By h value
closed_list = Set() # Explored
open_list.add(start)
🏁 Start
Add start to open list.
🧭 Select
Get node with smallest h (closest to goal).
🎯 Check
Is this the goal? Yes = done! No = continue.
🔀 Expand
Get neighbors. Skip explored ones.
🧮 Evaluate
Calculate h for each neighbor.
How Breadth-First Search Works
Breadth-First Search (BFS)
BFS explores a graph level by level, like ripples spreading from a stone dropped in water. It visits all nodes at distance 1 first, then distance 2, then distance 3, and so on.
Using a queue (FIFO), BFS guarantees finding the shortest path in unweighted graphs - where all edges have the same cost.
The Wave Pattern
Imagine dropping a stone in a pond - the waves spread outward evenly in all directions. BFS works the same way, exploring all directions equally before moving further from start.
Properties
- Optimal: Shortest path in unweighted graphs
- Complete: Always finds a path if exists
- Fair: Explores all directions equally
- High Memory: Stores all nodes at current level
Watch the demo! See how BFS expands like a wave - compare with DFS to see the difference!
1
# Breadth-First Search
2
function bfs(start, goal):
3
# Explore level by level
4
queue = Queue() # FIFO order
5
visited = Set() # Track visited
6
queue.enqueue(start)
7
visited.add(start)
8
9
while queue not empty:
10
# Get next node (FIFO)
11
current = queue.dequeue()
12
13
# Check if goal reached
14
if current == goal:
15
path = reconstruct_path(current)
16
return path # Found!
17
18
# Add all neighbors to queue
19
for each neighbor of current:
20
if neighbor not in visited:
21
visited.add(neighbor)
22
neighbor.parent = current
23
queue.enqueue(neighbor)
24
25
return null # No path found
🚀 Initialize
Create a queue and visited set. Add start to queue and mark as visited.
queue = Queue() # FIFO order
visited = Set() # Track visited
queue.enqueue(start)
visited.add(start)
🏁 Start
Create queue. Add start.
➡️ Dequeue
Take first node from queue.
🎯 Check
Is this the goal? Yes = done!
🔀 Expand
Get all unvisited neighbors.
➕ Enqueue
Add neighbors to back of queue.
How Depth-First Search Works
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It goes deep into the graph first, only exploring other paths when it hits a dead end.
Using a stack (LIFO), DFS is memory-efficient but doesn't guarantee finding the shortest path.
The Maze Explorer
Imagine exploring a maze by always turning the same direction (e.g., right) at every intersection. You'll eventually explore everything, but you might take long detours.
Properties
- Memory Efficient: Only stores current path
- Not Optimal: May find long detours
- Complete: Finds a path if exists (finite graphs)
- Fast for Deep Goals: Good when goal is far from start
Watch the demo! See how DFS dives deep before backtracking - compare with BFS!
1
# Depth-First Search
2
function dfs(start, goal):
3
# Go deep before going wide
4
stack = Stack() # LIFO order
5
visited = Set() # Track visited
6
stack.push(start)
7
8
while stack not empty:
9
# Get top of stack
10
current = stack.pop()
11
12
if current in visited:
13
continue # Skip if seen
14
visited.add(current)
15
16
# Check if goal reached
17
if current == goal:
18
path = reconstruct_path(current)
19
return path # Found!
20
21
# Push neighbors to stack
22
for each neighbor of current:
23
if neighbor not in visited:
24
neighbor.parent = current
25
stack.push(neighbor)
26
27
return null # No path found
🚀 Initialize
Create a stack and visited set. Push start node onto the stack.
stack = Stack() # LIFO order
visited = Set() # Track visited
stack.push(start)
🏁 Start
Create stack. Push start.
⬆️ Pop
Take top node from stack.
🎯 Check
Is this the goal? Yes = done!
🔀 Expand
Get all unvisited neighbors.
⬇️ Push
Push neighbors onto stack.
Test Your Knowledge
What does the formula f(n) = g(n) + h(n) calculate in A*?
1. What does the formula f(n) = g(n) + h(n) calculate in A*?
- ☐ A) Only the distance from start to current node
- ☐ B) The total estimated cost from start to goal via this node
- ☐ C) Only the estimated distance to the goal
- ☐ D) The number of walls between start and goal
2. Why is A* faster than Dijkstra in most cases?
- ☐ A) A* uses less memory
- ☐ B) A* skips walls automatically
- ☐ C) A* uses a heuristic to prioritize promising directions
- ☐ D) A* processes nodes in random order
3. What must be true about the heuristic h(n) for A* to guarantee the shortest path?
- ☐ A) It must never overestimate the actual cost (admissible)
- ☐ B) It must always equal zero
- ☐ C) It must be greater than g(n)
- ☐ D) It must be a random value
4. What is the Open List in A*?
- ☐ A) A list of walls in the grid
- ☐ B) A list of nodes that have already been fully explored
- ☐ C) A list of unreachable nodes
- ☐ D) A list of nodes discovered but not yet fully explored
5. When would Greedy Best-First Search fail where A* succeeds?
- ☐ A) When the grid is very large
- ☐ B) When obstacles create a trap that Greedy walks into
- ☐ C) When there is no path to the goal
- ☐ D) When start and goal are next to each other
6. What data structure does Depth-First Search (DFS) use?
- ☐ A) Queue (FIFO)
- ☐ B) Stack (LIFO)
- ☐ C) Priority Queue
- ☐ D) Hash Table
7. Which algorithm guarantees finding the shortest path in an unweighted graph?
- ☐ A) Depth-First Search (DFS)
- ☐ B) Greedy Best-First Search
- ☐ C) Breadth-First Search (BFS)
- ☐ D) None of the above
8. What is the main difference between Dijkstra and A*?
- ☐ A) Dijkstra is faster
- ☐ B) A* uses a heuristic to guide the search toward the goal
- ☐ C) Dijkstra only works on grids
- ☐ D) A* cannot find the shortest path
9. Why is DFS memory efficient compared to BFS?
- ☐ A) DFS visits fewer nodes
- ☐ B) DFS only needs to store the current path, not all nodes at a level
- ☐ C) DFS uses a smaller data structure
- ☐ D) DFS doesn't track visited nodes
10. Which statement about BFS is correct?
- ☐ A) BFS uses a Stack (LIFO)
- ☐ B) BFS explores nodes in order of their distance from the start
- ☐ C) BFS always finds the longest path
- ☐ D) BFS requires a heuristic function
Related Content
Article
Algorithmic Complexity
The lesson that an elegant algorithm beats any supercomputer — provided n is large enough.
Control Structures
Control structures: everything that decides between "do this" and "do that".
Data Structures II (Hierarchical & Networked)
Trees, search trees, and graphs — data structures with family relationships.
Rules & Logic: Expert Systems
AI before it learned from data: asked experts, wrote down rules, hoped.
Graph Search — The Beginnings
Graph search: the first thing AI could actually do — and still useful today.
Heuristics & Pathfinding: From Dijkstra to A*
How A* works — and why Dijkstra gets boring without a heuristic.
Linear Data Structures
The simplest ways to sort data — rows, stacks, and queues.
MinMax & Pruning
MinMax in practice: think backwards, assume the worst opponent, shortcut where possible.
Recursion
Recursion: the programming technique that looks simple until you understand it. And then too.
What Is an Algorithm?
What Euclid, IKEA instructions, and Google search have in common — all three are algorithms.
Demo
Swarm Intelligence (Boids)
See how three simple local rules give rise to the complex behavior of a bird flock.
MinMax (Game Theory)
Experience game theory hands-on: Play against an AI and watch how it calculates the optimal move.
Rule-Based AI
Collect clues and solve criminal cases through systematic application of rule-based logic. This interactive demo shows how AI systems reach solutions step by step.
Travelling Salesman: Algorithms in Competition
Place cities, draw your own route, and pit Greedy, Simulated Annealing and a Genetic Algorithm against you.