Lee Algorithm
The idea
Model the routing surface as a grid of cells, some blocked. From the source cell, expand a wave: mark every free neighbor with distance 1, their free neighbors with distance 2, and so on, a breadth-first search whose frontier forms rings of equal distance. The moment the target is labeled, stop and backtrace: from the target, repeatedly step to any neighbor with a smaller label until the source is reached. The labels guarantee each step descends by exactly one, so the traced path's length equals the target's label, which breadth-first order guarantees is the minimum possible.
Watch it work: the wave
Step through the expansion below. Each press of Step advances one distance ring; the number in each cell is its distance from the source. Three things to notice as you go: the wave spreads in every direction, including away from the target; it flows around the wall through the single gap like water; and the moment the target gets a label, that label is the shortest-path length, no checking required.
Watch it work: the backtrace
Now run the second phase. Starting at the target, each step moves to any neighbor whose label is exactly one smaller, downhill on the distance field, until the source is reached. Where two neighbors tie, either choice is fine: every downhill walk has exactly the same length, which is why Lee needs no tie-breaking cleverness to stay optimal.
Pros, cons, and the trade-off
Strengths
- Complete: if any path exists, the wave finds it. No configuration, no luck.
- Optimal: the found path is provably shortest; the target's label is the proof.
- Simple: a queue, a grid, and two passes. Easy to implement correctly, easy to trust.
- Unconditionally robust: any obstacle shape, any pin placement, no tuning parameters at all.
Weaknesses
- Explores everything: the wave visits cells proportional to the area around the pins, not the path length. Thousands of cells settled for a two-hundred-cell route.
- Memory per cell: a label for every grid cell (classically softened by Akers' trick of storing labels modulo 3, since the sequence 1,1,2,2,... still backtraces).
- Two pins at a time: multi-terminal nets need a Steiner decomposition first.
- Uniform costs only: no natural way to price vias, bends, or congestion. That upgrade is exactly what A* (A-star) adds.
The trade-off
Lee sits at the certainty-over-speed extreme of maze routing. Every successor pays for its exploration savings by giving something up: Hadlock and A* (A-star) keep the guarantees but need grid structure or an admissible estimate, Soukup surrenders shortest paths, Hightower surrenders completeness. Reach for Lee when being right matters more than being fast, and as the fallback when cleverer searches fail. See it live in the maze lab: Macro maze preset, watch the cells-explored counter.
Lineage
Everything in this family is an answer to Lee's exploration cost: Hadlock reorders the wave by detours, Soukup abandons breadth-first sprinting until blocked, and A* (A-star) prices distance-to-go into the queue. All keep his grid, his backtrace, and usually his guarantee.
Is it actually used today?
The literal 1961 algorithm and what ships differ on one point: cost uniformity. Production routing costs are never uniform (a via costs more than a straight step, wrong-way segments on a directioned layer cost more still, congested edges carry penalties), and the moment edges are weighted, plain breadth-first search stops being correct: real routers run Dijkstra and A (A-star) instead (TritonRoute documents an A-based search; Dr. CU runs Dijkstra over a sparse grid graph). What survives of Lee:
- The skeleton. Wavefront expansion plus backtrace is still the structure of every point-to-point engine, which is why the field calls that method "maze routing" in his honor.
- The last rung of the escalation ladder. Detailed routers try pattern routes first and widen the search when they fail; the final explore-everything rung is Lee-like in spirit, though even it runs weighted.
- Genuinely uniform-cost niches. Single-layer escape routing, some package and printed-circuit-board subproblems, and quick reachability checks still use the plain breadth-first form.
Lee is used today the way Dijkstra is used in navigation: nobody runs the textbook version, everybody runs its descendants.