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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (10): 10-12.

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

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

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

收稿日期:2007-11-20 修回日期:2007-12-28 出版日期:2008-04-01 发布日期:2008-04-01
通讯作者: 陆克中

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

摘要/Abstract

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

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

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

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

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.

[1]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[2]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[3]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[4]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[5]	张林霞，何利文，黄俊. 基于SDN网络的安全设备路由研究[J]. 计算机工程与应用, 2018, 54(4): 103-109.
[6]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[7]	应文杰，徐开，徐少平. 羽毛球机器人机械臂运动轨迹多目标规划[J]. 计算机工程与应用, 2017, 53(3): 258-265.
[8]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[9]	袁亚博，刘羿，吴斌. 改进蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2016, 52(6): 8-12.
[10]	韩建妙，刘业政. 基于遗传算法的超市最短导购路径推荐[J]. 计算机工程与应用, 2016, 52(4): 238-242.
[11]	孟颖翔1，高东怀2，许浩2，许卫中2. 基于最短路径的多子网链路层拓扑发现算法[J]. 计算机工程与应用, 2016, 52(2): 131-134.
[12]	侯晓琴1，胡志华1，高超峰1，罗勋杰2. 自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现[J]. 计算机工程与应用, 2016, 52(12): 31-36.
[13]	吴幸良，涂风华. 采用图模型的个性化标签推荐方法[J]. 计算机工程与应用, 2015, 51(9): 142-146.
[14]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[15]	耿显亚，许峰. 基于图论模型的一类集成电路布线算法[J]. 计算机工程与应用, 2015, 51(1): 21-25.