| 一种基于Dijkstra并行线程算法的研究与实现 |
| |
| 引用本文： | 李平,李永树.一种基于Dijkstra并行线程算法的研究与实现[J].测绘与空间地理信息,2014(9):50-53. |
| |
| 作者姓名： | 李平 李永树 |
| |
| 作者单位： | 西南交通大学地球科学与环境工程学院,四川成都,610031 |
| |
| 基金项目： | 高等学校博士学科点专项科研基金 |
| |
| 摘 要： | 针对传统Dijkstra算法运行效率的问题,提出了一种基于传统Dijkstra并行线程的算法,该算法动态地将交通网络进行子网分割。通过实验测试了不同网络节点数量和弧段数量下传统Dijkstra算法和本文算法运行时间,实验结果表明本文算法能够缩减网络节点搜索空间,降低算法的时间复杂度,提高算法的运行效率。
|
| 关 键 词： | Dijkstra算法 GIS 多线程 子网 时间复杂度 运行效率 |
Research and Implementation of On e Paar llel Thread Algorithm Based on Dijkstra |
| |
| LI Ping,LI Yong-shu.Research and Implementation of On e Paar llel Thread Algorithm Based on Dijkstra[J].Geomatics & Spatial Information Technology,2014(9):50-53. |
| |
| Authors: | LI Ping LI Yong-shu |
| |
| Institution: | LI Ping, LI Yong- shu (Earth Science and Environmental Engineering Academy of Southwest Jiaotong University, Chengdu 610031, China) |
| |
| Abstract: | Aiming at the problem of operating efficiency of traditional Dijkstra algorithm, the paper comes up with one algorithm of parallel thread based on traditional Dijkstra. The algorithm divises traffic network into subnets dynamically. Through experiment, the operating time of traditional Dijkstra algorithm is tested under different number of network junctions and arcs. The experiment has demonstrated that the algorithm can lower searching space of network junctions, reduce Dijkstra time complexity and improve Dijkstra operating efficiency. |
| |
| Keywords: | Dijkstra algorithm GIS multithreading subnet time complexity operating efficiency |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
