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

Time varying network shortest path algorithm based on priority queue

作　　者：杨传印 黄玮 薛少聪 王劲松 Yang Chuanyin;Huang Wei;Xue Shaocong;Wang Jinsong(School of Computer Science & Engineering, Tianjin University of Technology, Tianjin 300384, China;Tianjin Key Laboratory of Intelligent Computing & Novel Software Technology, Tianjin 300384, China)

机构地区：[1]天津理工大学计算机科学与工程学院,天津300384 [2]天津市智能计算和软件新技术重点实验室,天津300384

出　　处：《计算机应用研究》2019年第5期1403-1408,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(61673295;61301140);天津市大学生创新创业项目(201610060063)

摘　　要：提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。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.

关 键 词：时变网络 优先队列 最短路径 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]