Lee Algorithm (Wave Propagation) Pathfinding

Speed:

SlowFast

Start

End

Wall

Wavefront (Distance)

Visited (Distance)

Path

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(V + E), where V = vertices, E = edges

Space Complexity: O(V), for the queue and distance map

Optimal: Yes, finds shortest path in grid (unweighted)

Complete: Yes (will find solution if one exists)

How it works: Expands "wavefront" from start. Each cell records its distance and parent. Path reconstructed by backtracking.

Best for: Maze routing, grid-based shortest path, electronics, robotics.

Difference from BFS: Lee is BFS but highlights wave propagation and cell distances.

Implementation

function leeAlgorithm(grid, start, end) {
  const queue = [start];
  start.distance = 0;
  while (queue.length > 0) {
    const current = queue.shift();
    if (current === end) return reconstructPath(end);
    for (const neighbor of getNeighbors(current)) {
      if (neighbor.type !== "wall" && neighbor.distance === Infinity) {
        neighbor.distance = current.distance + 1;
        neighbor.parent = current;
        queue.push(neighbor);
      }
    }
  }
  return null;
}