Research And Application On Optimization For A Dijkstra-Based Automatic Routing Algorithm

As the rapid developing of computer industry, various CAD systems are becoming more and more popular, which is likely to replace traditional design techniques. In most of the CAD systems, such as circuit design system, it requires connecting many components to a whole device via routing. The researches about automatic routing come into being, because the integration density is growing higher and higher and routing is becoming more and more complicated, which is far more beyond the traditional manual routing.Any routing problem can be reduced to a shortest-path problem. The high efficiency and ease of implementation can be achieved, taking the advantage of the similarity of routing problem and shortest-path problem and applying the strategy to solve the shortest-path problem to the routing problem. After a thorough research about the shortest-path problem, this paper, based on Dijkstra, proposes an automatic routing optimizing algorithm with fast routing speed, high efficiency and ease of implementation. The method is that using the techniques like equipoint and relatively effective area reduces the vertex searching scale before taking the advantage of the Dijkstra-Based automatic routing algorithm. After the analysis to the lines' characteristics, introducing the ideal route,the value of the ideal route and the inflexions of the ideal route makes the algorithm that route quickly in time under special condition. The algorithm reduces the number of the points used in the grid to the utmost using the equivalence relation of points. This method is able to keep more points which are effective and can improve the rate of routing success to a certain extent. It also optimizes the algorithm by applying Adjacency List as the data storage structure after analysing the algorithm.The optimizing algorithm is already realized in the virtual experiment system of micro-processor principle and interface, and it is proven to be effective in improving the routing speed through practical application,theoretical analysis and program testing.