随着计算机工业的飞速发展,计算机越来越多的用于各种辅助设计,大有取代人工设计的趋势,而在各种计算机辅助设计系统如电路设计系统中,都需要布线将各种器件连接起来组成一个大的器件。随着各种器件的集成度越来越高,布线也越来越复杂,远非人工布线所能及。在这种情况下,关于自动布线的研究应运而生。对于任意的布线问题来说都可以把它归结于一个最短路径求解问题。利用布线问题与最短路径问题的相似性,将解决最短路径问题的方法用于解决布线问题,从而可保证较高的布通率并且容易实现。通过对最短路径求解问题的研究,可构建布线速度快、布通率高、容易实现的基于Dijkstra的自动布线优化算法。优化方法主要是在运用基于Dijkstra的自动布线算法之前,采用等价点、相对有效区域等方式来降低算法中需要搜索的网格点的规模。同时,通过对布线线条特点的分析,引入理想路径、理想路径值和理想路径拐点,使算法在一些特殊布线情况下能够及时快速的布线。利用两点之间的等价关系最大限度的降低线网占用的网格点,充分利用布线平台上已布线资源进行布线,留下更多的可用网格点,在一定程度上提高布线的布通率。通过对Dijkstra算法数据存储结构进行分析,选择邻接表作为网格点的存储结构,有效的避免了权值为无穷大的无效点,降低了算法的空间复杂度。基于Dijkstra的自动布线优化算法已经在微机原理与接口技术虚拟实验系统中实现,通过实际应用、理论分析和程序测试表明此算法在提高布线速度以及提升布通率方面具有良好的效果。