《计算机应用研究》|Application Research of Computers

基于优先队列的时变网络最短路径算法

Time varying network shortest path algorithm based on priority queue

免费全文下载 (已被下载 次)  
获取PDF全文
作者 杨传印,黄玮,薛少聪,王劲松
机构 1.天津理工大学 计算机科学与工程学院,天津 300384;2.天津市智能计算和软件新技术重点实验室,天津 300384
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)05-026-1403-06
DOI 10.19734/j.issn.1001-3695.2017.12.0804
摘要 提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。
关键词 时变网络; 优先队列; 最短路径
基金项目 国家自然科学基金资助项目(61673295,61301140)
天津市大学生创新创业项目(201610060063)
本文URL http://www.arocmag.com/article/01-2019-05-026.html
英文标题 Time varying network shortest path algorithm based on priority queue
作者英文名 Yang Chuanyin, Huang Wei, Xue Shaocong, Wang Jinsong
机构英文名 1.School of Computer Science & Engineering,Tianjin University of Technology,Tianjin 300384,China;2.Tianjin Key Laboratory of Intelligent Computing & Novel Software Technology,Tianjin 300384,China
英文摘要 This paper presented a time-varying network shortest path algorithm based on priority queue to solve the time-varying network shortest path problem which was difficult for traditional shortest path algorithm. The proposed algorithm could address optimal solution by using proposed time-window selection strategy which could select appropriate time window for the node to reduce the path length. Also, the algorithm used the priority queue to organize node set, which could improved the computational efficiency. Experiments on randomly generated network data and united state road data show that compared with classical algorithm, the proposed algorithm is not only able to obtain global optimal solutions, but also improve the speed of the algorithm.
英文关键词 time varying network; priority queue; shortest path
参考文献 查看稿件参考文献
 
收稿日期 2017/12/11
修回日期 2018/2/5
页码 1403-1408
中图分类号 TP183
文献标志码 A