An Efficient Constrained Shortest Path Algorithm for Traffic Navigation


Article Preview

FCD-based traffic navigation system is getting more and more attention from countries all over the world. Shortest path algorithm is one of the key techniques of a traffic navigation system. Since classical Dijkstra algorithm and heuristic A* algorithm cannot support some constrained conditions in practice, and existing algorithms supporting constraints require the road network to be modified ahead and have low efficiency. The paper studies the model of road network, and analyzes two types of constraints, one-way street and intersection turning prohibitions, then proposes the constrained A* algorithm and gives the Heuristic function. Finally, the paper tests and analyzes the algorithm, and evaluation performance of the prototype system which employs it. The result shows that the algorithm’s efficiency is fairly good.



Advanced Materials Research (Volumes 356-360)

Edited by:

Hexing Li, Qunjie Xu and Daquan Zhang




Z. H. Wang et al., "An Efficient Constrained Shortest Path Algorithm for Traffic Navigation", Advanced Materials Research, Vols. 356-360, pp. 2880-2885, 2012

Online since:

October 2011




[1] Junyu Dong, Study on link speed estimation in urban arteries based on GPS equipped floating vehicle, Master's degree paper, Chongqing University, 2006, In Chinese.

[2] Lee, T., Research on intelligent transportation systems in Taiwan, Control Conference, 2008, CCC 2008, 27th Chinese, (2008).


[3] Dijkstra, E.W., A note on two problems in connexion with graphs, Numerische Mathematik, 1959, 1(1), pp.269-271.


[4] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, Systems Science and Cybernetics, IEEE Transactions on, 1968, 4(2), pp.100-107.


[5] Yinzhen Li, Ruichun He, and Yaohuang Guo, Modeling for Shortest Path in Traffic Network with Node Limits, Operations Research and Management Science, 2005, vol 14(4).

[6] Xiangyang She, The shortest path algorithm with constraints, Computer Applications and Software, 2009, vol 26(5), In Chinese.

[7] Floyd, R.W., Algorithm 97: Shortest path. Commun, ACM, 1962, 5(6), p.345.