Lee algorithm

The Lee algorithm is one possible solution for maze routing problems.

1) Initialisation

 - Select start point, mark with 0
 - i := 0

2) Wave expansion

 - REPEAT
     - Mark all unlabeled neighbors of points marked with i with i+1
     - i := i+1
   UNTIL ((target reached) or (all points marked)

3) Backtrace

   - go to the target point
   REPEAT
     - go to next node that has a lower mark than the actual node
     - add this node to path
   UNTIL (start point reached)

4) Clearance

 - Block the path for future wirings
 - Delete all marks

Here is an example: http://www.princeton.edu/~wolf/modern-vlsi/Overheads/CHAP10-1/sld026.htm

Further information in Wayne Wolf, Modern VLSI Design, Prentice Hall, ISBN 0-13-061970-1, Page 518ff