Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (9): 2503-2507.DOI: 10.11772/j.issn.1001-9081.2015.09.2503

Previous Articles     Next Articles

Improved Dijkstra algorithm with traffic rule constraints

REN Pengfei1, QIN Guihe1, DONG Jinnan1,2, LI Bin1, ZHENG Xiaotian1   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun Jilin 130012, China;
    2. College of Communication Engineering, Jilin University, Changchun Jilin 130012, China
  • Received:2015-05-05 Revised:2015-06-02 Online:2015-09-10 Published:2015-09-17

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

任鹏飞1, 秦贵和1, 董劲男1,2, 李滨1, 郑啸天1   

  1. 1. 吉林大学 计算机科学与技术学院, 长春 130012;
    2. 吉林大学 通信工程学院, 长春 130012
  • 通讯作者: 董劲男(1980-),男,吉林长春人,讲师,博士,主要研究方向:智能控制、嵌入式系统、网络控制,dongjinnan@jlu.edu.cn
  • 作者简介:任鹏飞(1990-),男,内蒙古赤峰人,硕士研究生,主要研究方向:智能控制、嵌入式系统;秦贵和(1962-),男,山东高密人,教授,博士,CCF会员,主要研究方向:智能控制、嵌入式系统、汽车电子与信息技术;李滨(1991-),男,山东临沂人,硕士研究生,主要研究方向:智能控制、汽车电子与信息技术;郑啸天(1990-),男,陕西汉中人,硕士研究生,主要研究方向:智能控制、嵌入式系统。
  • 基金资助:
    2011年物联网发展专项。

Abstract: Traditional Dijkstra algorithm cannot adapt for the transportation network with traffic rule constraints during path planning. In order to solve this problem, based on the previous network models and algorithms, an improved Dijkstra algorithm with traffic rule constraints was proposed. It added new "to be selected state" and "renewable state" on the nodes, to solve the problem of nodes with traffic rule constraints. Meanwhile, grandfather node was introduced, thereby generating triples information of each node in the traffic network. Therefore, taking this as a backtrack basis, the shortest path from the starting node to the destination node could be obtained. This algorithm is not only applicable to the transportation network with traffic rule constraints but with low complexity. The correctness of the algorithm was verified through theoretical analysis. The effectiveness of the algorithm is verified through experimental tests carried out with actual traffic network in Chaoyang District of Changchun city and random added traffic rule constraints.

Key words: intelligent transportation, path planning, Dijkstra algorithm, traffic rule, triple of adjacent nodes

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

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

CLC Number: