• 先进计算 •

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

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

### Improved Dijkstra algorithm with traffic rule constraints

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

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.