When I first needed to route a wire between two points on a circuit board while avoiding obstacles, I discovered that this is a classic pathfinding problem with a dedicated, purpose-built solution: Lee’s algorithm. I think of it as breadth-first search wearing an engineer’s hat — it was designed specifically for maze routing in printed circuit boards and integrated circuits, and it guarantees the shortest path between a source and a destination on a grid, provided one exists. What I find compelling about it is how directly it maps an abstract graph-search technique onto a very physical, very practical engineering problem.
History and Background
I trace this algorithm to C. Y. Lee, who published it in 1961 in a paper titled “An Algorithm for Path Connections and Its Applications,” aimed at solving the wire-routing problem in circuit design. Around the same time, a very similar idea was independently described by Edward F. Moore for maze-solving, which is why this algorithm is sometimes referred to as the Lee-Moore algorithm. Both approaches are, at their core, applications of breadth-first search to a grid, but Lee’s specific formulation, with its wave-propagation framing and backtracing phase, became the standard technique taught in VLSI design and routing courses.
Problem Statement
I’m given a two-dimensional grid that represents a circuit board or maze, where some cells are blocked (obstacles) and others are free. I need to find the shortest path from a source cell to a destination cell, moving only through free cells, using moves restricted to up, down, left, and right (in circuit routing, this reflects how wires are laid on a grid). If no such path exists, I need to detect that too. Lee’s algorithm solves this by treating distance propagation as an expanding wave from the source, guaranteeing the shortest path is found the moment the wave reaches the destination.
Core Concepts
- Grid/Maze: the 2D array representing the board, where each cell is either free or blocked.
- Source and destination: the start and end cells I want to connect.
- Wave propagation: the process of expanding outward from the source cell in concentric “rings,” where all cells at distance
kare marked before any cell at distancek+1. - Cell labeling: each visited cell is marked with its distance from the source (its “wave number”).
- Backtracing: after reaching the destination, I retrace the path backward, always stepping to a neighboring cell with a distance exactly one less than the current cell’s distance, until I reach the source.
How It Works
I break Lee’s algorithm into two clear phases:
- Wave expansion (labeling) phase: starting from the source cell, I perform a breadth-first search, labeling each newly visited cell with a distance one greater than the cell that discovered it. I use a queue to process cells level by level, ensuring the wave expands uniformly in all four directions.
- Backtracing (path reconstruction) phase: once the destination is reached and labeled, I start from the destination and repeatedly move to any neighboring cell whose label is exactly one less than the current cell’s label, continuing until I arrive back at the source with label
0. This retraces one valid shortest path.
Working Principle
The reason this works is the same reason breadth-first search always finds shortest paths in unweighted graphs: because I explore cells strictly in order of increasing distance from the source, the first time I reach the destination, I am guaranteed to have done so via the shortest possible number of steps. The “wave” metaphor is apt because, physically, this is exactly how a wave of water or sound would spread outward from a point on a grid — reaching all points at distance 1 before any point at distance 2, and so on. The backtracing phase works because every cell’s label reflects the true shortest distance from the source, so walking from the destination to any neighbor with a strictly smaller label is guaranteed to make monotonic progress back to the source along an optimal path.
Mathematical Foundation
I formalize the grid as an unweighted graph G = (V, E), where V is the set of free cells, and E connects each cell to its up-to-four grid neighbors. Because all edges have equal weight 1, the length of a shortest path from source s to any cell v is exactly the BFS depth of v in this graph, satisfying the recurrence:
$$ d(v) = \min_{u \in N(v),\ d(u) \text{ known}} \big( d(u) + 1 \big) $$
where N(v) is the set of grid-adjacent free neighbors of v, and d(s) = 0.
The total number of cells labeled is at most |V| = R \times C for an R x C grid, and each cell is enqueued and dequeued exactly once, giving a total work bound of:
$$ T(R, C) = O(R \times C) $$
Diagrams
flowchart TD
A[Mark source cell with distance 0] --> B[Push source into queue]
B --> C{Queue empty?}
C -- Yes --> G[No path found]
C -- No --> D[Dequeue cell c]
D --> E{c is destination?}
E -- Yes --> H[Backtrace from destination to source]
E -- No --> F[For each unvisited free neighbor n of c: label n = label c + 1, enqueue n]
F --> CPseudocode
function leeAlgorithm(grid, source, destination):
R, C = dimensions of grid
dist = matrix of size R x C, initialized to -1 (unvisited)
dist[source] = 0
queue = empty queue
enqueue(queue, source)
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue is not empty:
current = dequeue(queue)
if current == destination:
break
for (dr, dc) in directions:
next = (current.row + dr, current.col + dc)
if next is within bounds
and grid[next] is free
and dist[next] == -1:
dist[next] = dist[current] + 1
enqueue(queue, next)
if dist[destination] == -1:
return "No path exists"
// Backtrace
path = [destination]
current = destination
while current != source:
for (dr, dc) in directions:
neighbor = (current.row + dr, current.col + dc)
if neighbor is valid and dist[neighbor] == dist[current] - 1:
path.append(neighbor)
current = neighbor
break
reverse(path)
return path
Step-by-Step Example
Consider a small 5x5 grid, where 0 marks a free cell and 1 marks an obstacle. Source is (0,0) and destination is (4,4):
0 0 1 0 0
0 1 1 0 0
0 0 0 0 1
1 1 0 1 0
0 0 0 0 0
Wave expansion: starting from (0,0) with distance 0, I expand outward. Cells (0,1) and (1,0) get distance 1. From there, the wave continues, respecting obstacles (1s block propagation). The wave eventually reaches (4,4) with some computed distance, say 10, after working around the obstacles.
Backtracing: starting at (4,4) with distance 10, I look for a neighbor with distance 9, then from there a neighbor with distance 8, and so on, until I reach (0,0) with distance 0. This traced-back sequence of cells is a valid shortest path.
Time Complexity
- Best case:
O(1)if source and destination are the same cell. - Average case:
O(R x C), whereRandCare the grid’s dimensions, since each cell is processed a constant number of times. - Worst case:
O(R x C)— every free cell may need to be visited once during the wave expansion phase; this bound holds regardless of obstacle placement.
Space Complexity
I need O(R x C) space for the distance/label matrix, plus O(R x C) in the worst case for the BFS queue, since in the worst case every free cell could be enqueued. The backtracing phase uses O(path length) additional space to store the reconstructed path, which is bounded by O(R x C) as well.
Correctness Analysis
Correctness follows directly from the well-established correctness of breadth-first search on unweighted graphs. Because I process cells strictly in non-decreasing order of distance (guaranteed by the FIFO queue discipline and by assigning each new cell exactly one more than its discoverer), the first time any cell — including the destination — is labeled, that label is guaranteed to be its true shortest distance from the source. This is proven formally by induction on distance level k: assuming all cells at distance less than k have been correctly labeled and dequeued before any cell at distance k is discovered, it follows that all cells at distance k are discovered only from correctly labeled distance k-1 cells, and so are themselves correctly labeled. The backtracing phase is correct because it follows a strictly decreasing sequence of valid distance labels back to 0, which by construction traces a path of minimum length.
Advantages
- Guarantees the shortest path on an unweighted grid, which is critical in circuit routing where wire length affects performance and cost.
- Conceptually simple and easy to implement using standard BFS machinery.
- Naturally handles arbitrary obstacle configurations without special-casing.
- Can be extended to multiple sources or multiple destinations with only minor modifications.
Disadvantages
- Memory-intensive for very large grids, since it needs to store a distance label for every cell.
- Doesn’t scale efficiently to problems requiring diagonal movement, weighted grids, or 3D routing without modification.
- In real VLSI design with millions of cells, straightforward Lee’s algorithm can be too slow and memory-heavy, prompting the use of more advanced routing heuristics.
- Doesn’t account for wire congestion, layer changes, or other physical routing constraints found in real circuit design without significant extension.
Applications
- Maze routing in printed circuit board (PCB) design and VLSI chip layout, which was the original motivating use case.
- Pathfinding in grid-based video games, robotics navigation, and warehouse robot routing.
- Network packet routing simulations on grid-like topologies.
- Any shortest-path problem on an unweighted grid with obstacles, such as maze-solving puzzles.
Implementation in C
#include <stdio.h>
#include <string.h>
#define ROWS 5
#define COLS 5
int grid[ROWS][COLS] = {
{0, 0, 1, 0, 0},
{0, 1, 1, 0, 0},
{0, 0, 0, 0, 1},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0}
};
int dist[ROWS][COLS];
int prevRow[ROWS][COLS];
int prevCol[ROWS][COLS];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
typedef struct { int r, c; } Cell;
int isValid(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == 0;
}
void leeAlgorithm(int srcR, int srcC, int destR, int destC) {
Cell queue[ROWS * COLS];
int front = 0, back = 0;
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < COLS; j++)
dist[i][j] = -1;
dist[srcR][srcC] = 0;
queue[back++] = (Cell){srcR, srcC};
while (front < back) {
Cell cur = queue[front++];
if (cur.r == destR && cur.c == destC) break;
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (isValid(nr, nc) && dist[nr][nc] == -1) {
dist[nr][nc] = dist[cur.r][cur.c] + 1;
prevRow[nr][nc] = cur.r;
prevCol[nr][nc] = cur.c;
queue[back++] = (Cell){nr, nc};
}
}
}
if (dist[destR][destC] == -1) {
printf("No path exists from source to destination.\n");
return;
}
printf("Shortest path length: %d\n", dist[destR][destC]);
/* Backtrace the path */
Cell path[ROWS * COLS];
int len = 0;
int r = destR, c = destC;
while (!(r == srcR && c == srcC)) {
path[len++] = (Cell){r, c};
int pr = prevRow[r][c];
int pc = prevCol[r][c];
r = pr;
c = pc;
}
path[len++] = (Cell){srcR, srcC};
printf("Path (source to destination):\n");
for (int i = len - 1; i >= 0; i--) {
printf("(%d,%d)", path[i].r, path[i].c);
if (i != 0) printf(" -> ");
}
printf("\n");
}
int main() {
leeAlgorithm(0, 0, 4, 4);
return 0;
}
Sample Input and Output
Input: the 5x5 grid shown earlier, source (0,0), destination (4,4).
Output:
Shortest path length: 8
Path (source to destination):
(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3) -> (3,2) -> (4,2) -> (4,3) -> (4,4)
(exact intermediate cells depend on the traversal order of directions during backtracing, though the path length is guaranteed minimal)
Optimization Techniques
- Bidirectional wave expansion: running the BFS wave from both the source and destination simultaneously and stopping when the waves meet can roughly halve the number of cells explored in practice.
- A* search as an alternative: when I have a good heuristic (like Manhattan distance on a grid), switching to A* search can drastically reduce the number of cells explored compared to plain Lee’s algorithm, while still guaranteeing shortest paths.
- Bit-packed grids: representing visited/blocked cells with bitmasks instead of full integers reduces memory footprint significantly on large boards.
- Hierarchical/coarse-grid routing: in real VLSI tools, the board is often partitioned into coarser regions first, with Lee’s algorithm applied only within a promising region, to avoid scanning the entire board.
Common Mistakes
- Forgetting to check grid boundaries before accessing neighbor cells, causing out-of-bounds errors.
- Not marking a cell as visited at the moment it is enqueued (rather than when dequeued), which can cause the same cell to be added to the queue multiple times.
- Confusing the “distance” label with a simple visited flag, losing the information needed for backtracing.
- Assuming diagonal movement is allowed by default — Lee’s algorithm classically restricts movement to four directions, and adding diagonals requires careful handling of “corner cutting” through obstacles.
Further Reading
- Lee, C. Y. “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers, 1961: https://ieeexplore.ieee.org/document/5219222
- GeeksforGeeks, “Lee Algorithm – Shortest path in a Maze”: https://www.geeksforgeeks.org/dsa/lee-algorithm-shortest-path-in-a-maze/
- Sherwani, N. A. “Algorithms for VLSI Physical Design Automation,” Springer: https://link.springer.com/book/10.1007/978-1-4757-2977-8
- Wikipedia, “Maze generation and solving algorithms” (background context): https://en.wikipedia.org/wiki/Maze_generation_algorithm
