Lee algorithm

The Lee algorithm is a solution to maze routing problems that is based on breadth-first search. It always gives an optimal solution if one exists, but it is slow and needs a lot of memory. The method has four stages. Initialization marks the start point with 0. Wave expansion then repeatedly marks every unlabeled neighbor of the points marked i with i plus 1, until the target is reached or no more points can be marked. Backtrace walks from the target to the start by always stepping to a neighboring node with a lower mark, adding each node to the path. Clearance finally blocks that path for future wirings and deletes all the marks. In chip layout the wave expansion marks only points in the routable area, not blocks or parts that are already wired, and to limit segmentation a route should keep to one direction as long as possible. The article cites a 1961 paper by C. Y. Lee on path connections and a 1974 paper by F. Rubin on the Lee path connection algorithm.