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

来源：计算机应用杂志2015年第9期北京时间：

作者：任鹏飞, 秦贵和, 董劲男, 李滨, 郑啸天

单位：1. 吉林大学 计算机科学与技术学院, 长春 130012;2. 吉林大学 通信工程学院, 长春 130012

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

关键词：智能交通,路径规划,Dijkstra算法,交通规则,节点三元组

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