Dijkstra最短路径算法  

The Shortest Path Algorithm Based on Dijkstra Algorithm

作　　者：裴志强[1] 冯海涛[1] 刘宝娟[1] 

机构地区：[1]中国电子科技集团公司第四十七研究所,沈阳110032

出　　处：《微处理机》2009年第5期98-100,共3页Microprocessors

摘　　要：随着现场可编程门阵列(Field Programmable Gate Array,FPGA)技术的不断发展,FPGA以其研发周期短、研发成本低等优势,正在许多应用领域逐步替代ASIC产品。随着FPGA阵列规模的扩大和应用领域的广泛,其配套软件的布局布线算法对于改善FPGA性能的重要性越来越显著。对FPGA布线算法进行了深入的研究,介绍了迷宫矩阵的建立、改进的Dijkstra迷宫探索算法,实现基于布通率、最短路径、时序约束等各种布线要求的目的,使其更有效的提高了FPGA的性能。FGPA is replacing ASIC circuits in many fields according to shorting development cycle and avoiding high cost,following Field Programmable Gate Array technology developing.When the size of FPGA is becoming larger and FPGA is wider in appliance fields,the arithmetic of place and route is more importance in software to improve performance and function.This article presents FPGA auto routing algorithm base of Dijkstra algorithm,satisfies all sorts of routing needs,which bases the shortest path,timing constraint and so on. Dijkstra algorithm makes it availability about improving the capability of FPGA.

关 键 词：现场可编程门阵列(FPGA) 迷宫矩阵 最短路径算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]