| 一种限制搜索区域的最短路径改进算法 |
| |
| 引用本文： | 王海梅,周献中.一种限制搜索区域的最短路径改进算法[J].南京理工大学学报(自然科学版),2009,33(5). |
| |
| 作者姓名： | 王海梅 周献中 |
| |
| 作者单位： | 1. 南京理工大学,自动化学院,江苏,南京,210094
2. 南京大学,控制与系统工程系,江苏,南京,210093 |
| |
| 摘 要： | 最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。
|
| 关 键 词： | 最短路径 Dijkstra算法 矩形限制搜索区域 比值系数 |
Improved Shortest Path Algorithm for Restricted Searching Area |
| |
| WANG Hai-mei,ZHOU Xian-zhong.Improved Shortest Path Algorithm for Restricted Searching Area[J].Journal of Nanjing University of Science and Technology(Nature Science),2009,33(5). |
| |
| Authors: | WANG Hai-mei ZHOU Xian-zhong |
| |
| Institution: | 1.School of Automation;NUST;Nanjing 210094;China;2.Department of Control and Systems Engineering;Nanjing University;Nanjing 210093;China |
| |
| Abstract: | Algorithmic efficiency of the shortest path searching is a problem which has brought wide attention and needs to be resolved urgently in many application fields.Based on the classical Dijkstra's shortest path algorithm,the optimization means is analyzed.A restricted rectangle searching area algorithm is proposed to reduce the searching area.In order to improve the running efficiency,variational ratio coefficients are used during path searching to adapt the characteristic of the road network path searching.T... |
| |
| Keywords: | shortest path Dijkstra algorithm restricted rectangle searching area ratio coefficients |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
