具有交通规则约束的改进Dijkstra算法

作     者：任鹏飞 秦贵和 董劲男 李滨 郑啸天 REN Pengfei;QIN Guihe;DONG Jinnan;LI Bin;ZHENG Xiaotian

作者机构：吉林大学计算机科学与技术学院长春130012 吉林大学通信工程学院长春130012 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2015年第35卷第9期

页      面：2503-2507页

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：2011年物联网发展专项 

主　　题：智能交通 路径规划 Dijkstra算法 交通规则 节点三元组 

摘      要：传统Dijkstra算法在路径规划时无法适用于具有交通规则约束的交通网络。为解决该问题,在以往的路网模型和算法的基础上,提出一种具有交通规则约束的改进Dijkstra算法。算法对节点新增待选择状态和可再更新状态,用以解决节点具有交通规则约束的问题;同时引入祖父节点,从而生成交通网络中各节点的三元组信息,以此作为回溯依据,可以得到从初始节点到目的节点的最短路径。该算法不仅适用于具有交通规则约束的交通网络,且具有较低的复杂度。通过理论分析证明了算法的正确性,并以长春市朝阳区的实际交通网络和随机添加的交通规则约束为数据进行了实验测试,验证了算法的有效性。