CoreSource checked

Lee Algorithm

Finds shortest paths on a grid by expanding wavefront distances.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Beginner
Family: Wavefront Pathfinding
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 1
Code example: Not ready
Visualization: Ready

Overview

The Lee Algorithm is a breadth-first grid routing method that labels cells by distance from the start.

Core Concepts

distance relaxationgrid frontierqueue frontierwavefront pathfindingroute costfrontier expansionpath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(w h)

Average

O(w h)

Worst

O(w h)

Space

O(w h)

When to Use

Use Lee Algorithm when you need to expand a wavefront through grid cells.
Use it for maze routing with inputs like grid with blocked cells.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the Wavefront Pathfinding tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when the required output is not shortest grid path.

What It Does

Expands a wavefront through grid cells
Backtracks from the target along decreasing distances

Use Cases

Maze routing
Circuit board routing
Grid shortest paths

Inputs

Grid with blocked cells
Start and target cells

Outputs

Shortest grid path
No-path result

Key Formulas (1)

Wavefront distance

distance_[neighbor] = distance_[current] + 1

distance[neighbor] = distance[current] + 1

Assigns each newly reached grid cell the next distance from the source.

Pseudocode

1.Place the start cell in a queue
2.Label neighbors with distance plus one
3.Continue until the target is reached or the queue empties
4.Backtrack from the target through decreasing labels
5.Return the path

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Lee Algorithm: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Grid with blocked cells; Start and target cells.
Use this step as the implementation spine: Place the start cell in a queue.
Then preserve the next state change: Label neighbors with distance plus one.
Store predecessor links if the final path is needed, not just the final distance.

Common Pitfalls

Lee Algorithm is reliable but memory-heavy on large grids.
Treating a visited node as final before its best known cost is actually settled.
Handle empty, invalid, and boundary inputs before trusting shortest grid path.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show distance labels spreading across a grid from the start.

Step 1 of 5: Place the start cell in a queue

grid-wavefront

Notes

Lee Algorithm operates in O(w h) time and O(w h) space within the Wavefront Pathfinding family. Key governing relation: distance[neighbor] = distance[current] + 1. Often compared with Breadth-First Search and Jump Point Search.