Electronic Design Automation

12.3.1. Maze routing

Perhaps the most widely used algorithm for finding a path between two points is the maze-routing algorithm (also called Lee's algorithm) [Lee 1961], which is based on the breadth-first-search (BFS) technique.

Maze routing adopts a two-phase approach of filling followed by retracing. The filling phase works in the “wave propagation” manner. Starting from the source node S, the adjacent grid cells are progressively labeled one by one according to the distance of the “wavefront” from S until the target node T is reached. Figures 12.6a and b illustrates the “wave propagation” when the labels of “wavefronts” reach 2 and 3, respectively. Once the target node T is reached, a shortest path is then retraced from T to S with decreasing ...