Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms - Coggle Diagram
Pathfinding Algorithms
Search Trees & State Space
Branch = action
Node = state
Frontier: unexplored leaf nodes
Use a queue/lookup table to track:
Node state
Parent node
Action taken
Path cost
Algorithm Performance Measures
Completeness – Will it always find a solution?
Optimality – Is the path cost minimal?
Time complexity – Execution speed
Space complexity – Memory usage
Uninformed Search (Blind)
Breadth-First Search (BFS)
FIFO queue
Guaranteed shortest path
High memory usage
Uniform Cost Search
Expands node with lowest path cost
Depth-First Search (DFS)
LIFO stack (backtracking)
Uses less memory
Can loop infinitely
Informed Search (With Heuristics)
Best First Search
Uses evaluation function f(n)
Heuristic h(n) = estimated cost to goal
Greedy Best First Search
Chooses node with lowest h(n)
Fast but not always optimal
A* (A-Star) Search
f(n) = g(n) + h(n)
g(n) = cost so far
h(n) = estimated cost to goal
Optimal and complete
Dijkstra’s Algorithm
Modified BFS for weighted graphs
Builds shortest path using:
Edge weights
Relaxation
Doesn't use heuristics
Similar to A* with h(n) = 0
Heuristics
Guide the search to improve speed & accuracy
Must underestimate cost for A* to be optimal
Applications & Examples
Game development (tower defense, grid navigation)
Traffic control
Puzzle solving (e.g., 8-puzzle)
Network optimization
AI in robotics
Slime Mould – bio-inspired efficient routing