Shortest path algorithm of urban traffic network based on turning restriction

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (10): 10-12.

• 博士论坛 • Previous Articles Next Articles

Shortest path algorithm of urban traffic network based on turning restriction

LU Ke-zhong¹,SUN Hong-yuan¹,LIN Xiao-hui²,LI Xu-yang³

1.Super Computing Center，Shenzhen University，Shenzhen，Guangdong 518060，China
2.College of Information Engineering，Shenzhen University，Shenzhen，Guangdong 518060，China
3.Shenzhen Tencent Science and Technology Co. Ltd.，Shenzhen，Guangdong 518085，China

Received:2007-11-20 Revised:2007-12-28 Online:2008-04-01 Published:2008-04-01
Contact: LU Ke-zhong

一种基于转向限制的城市交通网最短路径算法

陆克中¹,孙宏元¹,林晓辉²,李旭阳³

1.深圳大学超级计算中心，广东深圳 518060
2.深圳大学信息工程学院，广东深圳 518060
3.深圳腾讯科技有限公司，广东深圳 518085

通讯作者: 陆克中

Abstract

Abstract: A model of weighted digraph is proposed to satisfy actual navigation requirement of urban traffic network.Vertices in digraph not only include crossing，but also include start point and end point.A shortest path algorithm of urban traffic network based on turning restriction is proposed.The algorithm is improved on Dijkstra algorithm.The condition of turning restriction is adapted by adding virtual vertices.Experiment shows the algorithm is right.

Key words: urban traffic network, turning restriction, shortest path, weighted digraph

摘要： 针对城市交通网导航的实际需要，提出了有向加权图的模型，图中顶点不仅包括路口，还包括起点和终点，并对Dijkstra算法进行改进，提出了一种基于转向限制的城市交通网最短路径算法，通过加入虚拟顶点，从而适应转向限制的条件。实验表明了该算法的正确性。

关键词: 城市交通网, 转向限制, 最短路径, 有向加权图

LU Ke-zhong¹,SUN Hong-yuan¹,LIN Xiao-hui²,LI Xu-yang³. Shortest path algorithm of urban traffic network based on turning restriction[J]. Computer Engineering and Applications, 2008, 44(10): 10-12.

陆克中¹,孙宏元¹,林晓辉²,李旭阳³. 一种基于转向限制的城市交通网最短路径算法[J]. 计算机工程与应用, 2008, 44(10): 10-12.

[1]	LI Jun. Improved Social Force Crowd Evacuation Simulation Model Combined with Shortest Path [J]. Computer Engineering and Applications, 2021, 57(8): 264-270.
[2]	YE Yingshi, WEI Fuyi, CAI Xianzi. Research on Fast Dijkstra Algorithm Based on Parallel Computing [J]. Computer Engineering and Applications, 2020, 56(6): 58-65.
[3]	LI Yan, WANG Yangyang, ZHANG Hongyan, WU Youxi. Fast Pruning Algorithm for Unreachable Vertices and Its Application in Solving Shortest Path Problem [J]. Computer Engineering and Applications, 2020, 56(15): 51-57.
[4]	MA Xuan, LIU Dong, HU Jiaxin. Particle Swarm Optimization for Solving Problem of k-Shortest Paths via Designated Points [J]. Computer Engineering and Applications, 2019, 55(20): 89-94.
[5]	ZHANG Xin, YAN Pei, GUO Yang, WANG Huihui. K-Shell Shortest Path Approximation Algorithm for Complex Networks [J]. Computer Engineering and Applications, 2019, 55(14): 54-60.
[6]	ZHANG Linxia, HE Liwen, HUANG Jun. Route of security device research based on SDN Network [J]. Computer Engineering and Applications, 2018, 54(4): 103-109.
[7]	GAO Zunhai, GAO Ying, CHENG Guo. Weighted path matrix of graph and all pairs shortest path problem [J]. Computer Engineering and Applications, 2017, 53(9): 47-50.
[8]	YING Wenjie, XU Kai, XU Shaoping. Multi-objective trajectory planning of manipulator for badminton robot [J]. Computer Engineering and Applications, 2017, 53(3): 258-265.
[9]	DONG Yuehua, ZHOU Yongxin. Selective sorting algorithm over a set of necessary nodes [J]. Computer Engineering and Applications, 2017, 53(20): 43-49.
[10]	YAO Bo1, FENG Hongwei1, GAO Yuan2, MA Jiali1, FENG Jun1. Dynamic pruning search algorithm that must go through certain node set [J]. Computer Engineering and Applications, 2017, 53(15): 57-62.
[11]	YANG Nan1, CHEN Yuanbo2, WANG Yanjie2, LI Qing2. Multipath transmission protocol based on degree-constrained shortest path tree [J]. Computer Engineering and Applications, 2017, 53(11): 126-130.
[12]	YUAN Yabo, LIU Yi, WU Bin. Solving shortest path problem with modified ant colony algorithm [J]. Computer Engineering and Applications, 2016, 52(6): 8-12.
[13]	MENG Yingxiang1, GAO Donghuai2, XU Hao2, XU Weizhong2. Link layer topology discovery for multi-subnet networks based on shortest path [J]. Computer Engineering and Applications, 2016, 52(2): 131-134.
[14]	HOU Xiaoqin1, HU Zhihua1, GAO Chaofeng1, LUO Xunjie2. Priority-based genetic algorithm for routing automated guided vehicles for traversing blocks in warehouse aisles [J]. Computer Engineering and Applications, 2016, 52(12): 31-36.
[15]	WU Xingliang, TU Fenghua. Personalized tag recommendation method using graph-model [J]. Computer Engineering and Applications, 2015, 51(9): 142-146.

Shortest path algorithm of urban traffic network based on turning restriction

一种基于转向限制的城市交通网最短路径算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics