摘要： 提出了基于Dijkstra最短路径算法的动态权值最短路径算法,并对该算法提出了优化措施。基于优化的最短路径算法,在芯片分析软件中实现了逻辑图中的两点间自动布线的功能,并在此基础上实现了拖动元件过程中的重布线功能。该算法能够在尽量减少布线交叉和转角的基础上减少布线长度,使得逻辑图清晰易读,提高了芯片反向工程后端电路分析的效率。

关键词: 最短路径, 逻辑图, 布线, 权值

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 in practice and helps to improve the IC analysis efficiency.The experience shows that the final logic diagram is quite impressive as for the readability and traceability.

中图分类号: 

• TP311.52