Lee algorithm
 | Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation. |
 | This article has not been added to any content categories. Please help out by adding categories to it so that it can be listed with similar articles. |
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
- Of course the wave expansion marks only points in the routable area of the chip, not in the blocks or already wired parts
- to minimize segmentation you should keep in one direction as long as possible
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