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

来源：计算机应用研究杂志2019年第5期北京时间：

作者：杨传印,黄玮,薛少聪,王劲松,

单位：1.天津理工大学计算机科学与工程学院,天津300384；2.天津市智能计算和软件新技术重点实验室,天津300384；

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

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

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