Offensive Security Researcher & Quantum Cryptography Analyst

Lee Algorithm: Working, Explanation, and Shortest Path in Grid

Abdul Wahab Junaid
lee algorithm and working of this algorithm

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

How It Works

I break Lee’s algorithm into two clear phases:

  1. 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.
  2. 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 --> C

Pseudocode

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

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version