DW最短路径算法及在逻辑图自动布线中的应用 郑 爽，张卫山 （同济大学软件学院，上海 200331） 摘 要：提出了基于 Dijkstra 最短路径算法的动态权值最短路径算法，并对该算法提出了优化措施。基于优化的最短路径算法，在芯片分 析软件中实现了逻辑图中的两点间自动布线的功能，并在此基础上实现了拖动元件过程中的重布线功能。该算法能够在尽量减少布线交叉 和转角的基础上减少布线长度，使得逻辑图清晰易读，提高了芯片反向工程后端电路分析的效率。 关键词：最短路径；逻辑图；布线；权值 DW Shortest Path Algorithm and Its Application in Logic Diagram Routing ZHENG Shuang, ZHANG Weishan (School of Software Engineering, Tongji University, Shanghai 200331) 【Abstract】The dynamic weight shortest path algorithm (DW-SPA) is presented based on the Dijkstra’s shortest path algorithm. Two approaches to improve the performance of the algorithm are introduced. With DW-SPA the automatic routing between two points and rerouting while moving the component in the logic diagram are conducted efficiently. At the same time this algorithm can be used for reducing or minimizing crossovers and turns while minimizing routing length. DW-SPA is used successfully i
