Lee's algorithm

If you ever get stuck in a large maze, don't panic and hope to find a chocolate bar in your pocket: that's the only advice we can give you. However, if you get yourself into a situation in a virtual maze, this topic might offer you some assistance. The Lee algorithm is one of the possible solutions for the maze routing problem — finding the shortest path between two points on a 2D grid:

The red squares $S$ and $T$ on the grid above correspond to the Start and Target points. The blue squares represent obstacles.

The Lee algorithm is used in computer-aided design systems to route wires on printed circuit boards, in the game industry (especially for real-time strategies) and other areas. In this topic, we will learn about this algorithm and, to get a better understanding, apply it for the grid above. So, let's start moving towards the target!

Lee algorithm: part 1

The first part of the Lee algorithm is finding the length of the shortest path between the start and the target point. Finding it is a step-by-step process: we need to begin from the start, find the distances to the neighboring points first, then calculate the distances to the next neighboring points and so on, until the target point is finally reached.

At the first step, the labels of all neighboring points of $S$ are set to $1$ indicating that the shortest distances are equal to $1$. After that, we consider all neighbors of points with the label $1$ and set their labels to $2$ indicating that the shortest distances from the start point are equal to $2$. The figure below shows the grid after these two steps:

This procedure continues until the target point is reached. After that, the grid will look like this:

Now we know that the length of the shortest path between $S$ and $T$ is $7$.

To sum up, the steps of the first part of the Lee algorithm are:

1. Label the start point with $0$.
2. Initialize a variable $i$ with $0$.
3. Consider all unlabeled neighbors of points with label $i$ and set their labels to $i + 1$.
4. Set $i$ to $i + 1$.
5. Repeat steps 3-4 until the target point is reached.

Pseudocode for Lee algorithm: part 1

The initial steps of the Lee algorithm are crucial for establishing the groundwork of the shortest path discovery. We begin by labeling the start point with `0` and iteratively assign labels to neighboring points in a stepwise manner until the target point is reached. The pseudocode below outlines the implementation details of this process.

// Function to perform the first part of Lee algorithm
function LeeAlgorithmPart1(grid, start, target):
    // Initialize the grid with labels
    labels = initializeLabels(grid, start)

    // Initialize the current label
    currentLabel = 0

    // Lee algorithm part 1
    while labels[target.x][target.y] == null:
        processCurrentLabel(grid, labels, currentLabel)
        currentLabel = currentLabel + 1

// Function to initialize labels on the grid
function initializeLabels(grid, start):
    // Create a 2D array for labels with null values
    labels = createEmptyArray(grid.rows, grid.columns)

    // Set the label of the start point to 0
    labels[start.x][start.y] = 0

    return labels

// Function to process points with the current label
function processCurrentLabel(grid, labels, currentLabel):
    // Iterate through the grid
    for each point (x, y) in grid:
        if labels[x][y] == currentLabel:
            // Consider unlabeled neighbors and set their labels
            setNeighborsLabels(grid, labels, currentLabel + 1, (x, y))

// Function to set labels for unlabeled neighbors
function setNeighborsLabels(grid, labels, newLabel, point):
    // Define the possible neighbors
    neighbors = getUnlabeledNeighbors(grid, labels, point)

    // Set the labels for neighbors to the new label
    for each neighbor in neighbors:
        labels[neighbor.x][neighbor.y] = newLabel

// Function to get unlabeled neighbors of a point
function getUnlabeledNeighbors(grid, labels, point):
    // Define the possible directions
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    // Initialize the list of neighbors
    neighbors = []

    // Iterate through possible directions
    for each direction in directions:
        neighbor = (point.x + direction.x, point.y + direction.y)
        // Check if the neighbor is within the grid and is unlabeled
        if isValidNeighbor(grid, labels, neighbor):
            neighbors.add(neighbor)

    return neighbors

// Function to check if a neighbor is valid and unlabeled
function isValidNeighbor(grid, labels, neighbor):
    // Check if the neighbor's row index is within the grid
    // Check if the neighbor's column index is within the grid
    if (neighbor.x >= 0 and neighbor.x < grid.rows) and (neighbor.y >= 0 and neighbor.y < grid.columns): 
        // Check if the neighbor is unlabeled
        if labels[neighbor.x][neighbor.y] == null:
            return true

    return false

// Function to create an empty 2D array
function createEmptyArray(rows, columns):
    // Initialize an empty 2D array with null values
    array = new Array(rows)
    for i from 0 to rows:
        array[i] = new Array(columns)

    return array

Lee algorithm: part 2

Next, we need to reconstruct the shortest path between the start and the target points. To do this, we start with the target point and move to any neighboring point with a label one fewer than the label of the current point. This process continues until the start point is reached. The figures below show the first two steps; the green points correspond to the beginning of the shortest path between $S$ and $i + 1$.

After the procedure is completed, the grid will look like this:

Note that in some cases, there are several possible directions to choose from. This means that there might be several shortest paths between the start and the target points (just like in life).

So, the steps of the second part of the Lee algorithms are:

1. Set the target point as current.
2. Initialize a variable $i$ with the label of the target point.
3. Consider all neighbors of the current point and move to any with a label $i-1$.
4. Set $i$ to $i-1$.
5. Repeat steps 3-4 until the start point is reached.

Pseudocode for Lee algorithm: part 2

The second part of the Lee algorithm involves moving backward from the target point to the start point, considering neighbors with labels one fewer than the current label. The pseudocode below outlines the implementation details of this process.

// Function to perform the second part of Lee algorithm
function LeeAlgorithmPart2(grid, start, target):
    // Set the target point as current
    current = target

    // Initialize the label variable
    currentLabel = labels[current.x][current.y]

    // Lee algorithm part 2
    while current != start:
        // Move to any neighbor with a label one fewer than the current label
        current = moveToNeighborWithLabel(grid, labels, current, currentLabel - 1)
        
        // Update the current label
        currentLabel = currentLabel - 1

// Function to move to a neighbor with a specific label
function moveToNeighborWithLabel(grid, labels, current, targetLabel):
    // Define the possible neighbors
    neighbors = getNeighborsWithLabel(grid, labels, current, targetLabel)

    // Move to the first neighbor (choose any if multiple). 
    // Here, we have just arbitrarily chosen the first neighbor.
    return neighbors[0]

// Function to get neighbors with a specific label
function getNeighborsWithLabel(grid, labels, current, targetLabel):
    // Define the possible directions
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    // Initialize the list of neighbors
    neighbors = []

    // Iterate through possible directions
    for each direction in directions:
        neighbor = (current.x + direction.x, current.y + direction.y)
        // Check if the neighbor is within the grid and has the target label
        if isValidNeighbor(grid, labels, neighbor) and labels[neighbor.x][neighbor.y] == targetLabel:
            neighbors.add(neighbor)

    return neighbors

// Function to check if a neighbor is valid. We do this by checking if the neighbor is within the grid.
function isValidNeighbor(grid, labels, neighbor):
    // Check if the neighbor's row index is within the grid
    // Check if the neighbor's column index is within the grid
    if (neighbor.x >= 0 and neighbor.x < grid.rows) and (neighbor.y >= 0 and neighbor.y < grid.columns): 
       return true

    return false

Complexity analysis

For a grid of size $n \times m$, time and space complexity of Lee algorithm is $O(n \cdot m)$ since we need to store an array of distances for all $n \times m$ points of the grid, and in the worst case all these points might be processed.

To better understand the steps of the algorithm, take a look at a visualization (where the described algorithm corresponds to the Breadth-First-Search option on the right pane.)