最短路径问题是网络分析中的一个重要问题，求解该问题的方法有很多，目前公认的、较优的求解方法是著名的算法。该算法是基于图论中的网络模型，在求解时Dijkstra 有可能并准备搜索所有的网络节点，算法的时间复杂度为 O(N 2，为网络节点数)N [1]。所以在城市道路网节点数较大的情况下，算法求解速度慢，花费时间长，效率低。而实际有些系统，如我们研发的基于城市道路网的自主车辆导航系统，要求快速地为车辆规划出从起点到终点的最短距离行驶路径，即路径规划的快速性要求较高，显然算法很Dijkstra 难满足快速要求[2]。 城市道路网一方面包含网络本身的拓扑特征，另一方面还包含了大量的反映地理位置特征的经纬度数据以及与应用有关的数据。所以，快速求解道路网两节点间的最短路径，应考虑道路网本身特点[3]。本文根据道路网的特点，采用双向搜索和投影法，提出一种快速地求解最短路径的算法。该算法搜索空间小，求解速度快，算法的时间复杂度不超过 ，在实际自主车辆导航系统中的应用证明了算法的实O(N)用性和可靠性。
矢量化的城市道路网的存储
1 计算机不可能从位图中寻路径，因为位图仅保存了点
的信息，点与点间的拓扑关系没有体现。计算机存储的是矢量化的城市道路网图，由节点、边及相应的拓扑关系构成的。节点是道路的交叉点或端点，有相对的经度、纬度地理坐标；边是两节点间的一段道
路，用于表示分段道路，边的权值定义为道路距离。所有的边都是直线段，对于实际道路网中弯曲较大的路段，可在路段上插入一系列节点，于是该路段由一些弧度较小的路段构成，弧度较小的路段可视为一条边[3]。
道路网图的存储方法是影响算法搜索速度和时间复杂度的一个重要因素。根据算法的特点，对道路网图中的每一个
节点进行编号，采用邻接表的链式存储结构[1]。在邻接表中，对图中的每个节点建立一个单链表，每个单链表都有表结点和表头结点构成。第个单链表的个表结点表示和图中i w 第个节点相关联的条边。链表的表头结点以顺序结构形式i w 存储，以便随机访问图中任一节点的单链表。因此，采用邻接表的链式存储结构，很容易到和图中任一节点相关联的边，便于算法的编程实现。单链表的表头结点和表结点的结构如下：
表头结点表结点
：节点编号；：节点位置坐标；：指向链表
Name Position First 中的第一个表结点；指向链表中的下一个表结点；边Next: weight：的权值。
算法描述
2 算法的基本思想
2.1 从几何学中知道，两点间直线最短。在道路网图中，如果两节点间存在一条边，则该边为两节点间的最短路径。若不存在一条边，则连接两节点的直线段代表了一个路线的趋势，顺着连线方向的某条边是最短路径的可能性较大[3]。
算法采用双向搜索，从起点进行正向搜索，同时从终S 点进行逆向搜索。两个方向在每一步都要搜索和指定的直T 线段夹角最小的边或搜索和直线段左右两侧各一条夹角最小的边，并利用投影法来判断双向搜索是否能会合。会合后，从搜索到的起点到终点的路径中取距离最短的路径为所求解。若不能会合，则从当前节点继续搜索，直到终点或起T 点，取两个方向搜索到的距离最短的路径为所求解。
S 基于城市道路网的快速路径寻优算法
毕军 1，付梦印1，周培德2，张宇河1
北京理工大学自动控制系；北京理工大学计算机科学与工程系，北京）
(1. 2. 100081摘要 ：从城市道路网的特点出发，描述了矢量化的城市道路网的存储结构，提出一种求解城市道路网两节点间最短路径的算法。算法基于双向式搜索原理，采用投影法、夹角最小的方法及二叉树理论。和算法相比，算法大大减小搜索空间，提高搜索速度，时间复杂性Dijkstra 不超过，为网络节点数。实际应用表明算法有O(N)N 很强的实用性和可靠性。关键词：最短路径；路径规划；城市道路网
A Fast Algorithm for Optimum Path Based on a City Road Net
BI Jun 1，FU Mengyin 1，ZHOU Peide 2，ZHANG Yuhe 1
；(1.Department of Automatic Control, Beijing Institute of Technology
2.Department of Computer Science and Engineering, Beijing Institute of Technology, Beijing 100081)
【】Abstract According to the characteristics of a city road net, this paper discusses a kind of data structure of road net and proposes an algorithm for seeking the shortest path between two points in the road net. The algorithm takes advantage of the theories of bidirectional search, projection, minimum angle and binary tree. Compared with Dijkstra algorithm, the algorithm can reduce seeking space and can raise seeking speed greatly, and its time complexity can not exceed O(N), while N is t
he number of road net points. The application results show that the algorithm has good practicability and reliability.【】；；Key words Shortest path Path planning City road net
第28卷 第12期Vol.28 № 12计 算 机 工 程Computer Engineering
2002年12月 December 2002
· 博士论文·
中图分类号： TP301.6
文章编号：1000—3428(2002)12 —0036—03
文献标识码：A
—36—
Next
Weight
Position
Name
Position
Weight
Next
算法实现
2.2 输入：采用邻接表结构存储的矢量化的道路网。起点、终点为网络中任意指定的两个节点。
S T 输出：与之间的一条最短路径及其长度。
S T 步：1ST ST 连接和成直线段，计算的长度，设长
S T 度值为，设计数变量。定义起点为原点，终点为目K i=1S T 标点。
步：2如果与之间存在一条边，则该边即为所求路S T 径，否则，转步。
3步：3分别从出发正向搜索、出发逆向搜索寻S ()T ()与ST 、TS 夹角最小的边。该边的另一端点A i ,B i 称为活动(点至)ST 、TS 的投影点A'i ，B'i ，计算SA'i 始终为原点，(S )TB'
i i αi β始终为目标点的长度，分别设为。(T
) , 步：4将|SA i
|i α始终为原点，作为活动点(S ) A i 的两个标
记；TB'i i β始终为目标点作为活动点(T ), B i 的两个标记。即
活动点的第一个标记是原点或目标点至该活动点子路径上V 所有边的权值之和，第二标记是的当前边的活动点在V ST 或TS 上的投影点与原点或目标点间的长度。
步：5用 A i ,B i 分别代替然后计数变量自增，
。S,T,i i=i+1重复步至步，但步中的活动点总是投影到原点、目标点243的直线段ST 或TS 上，直至A u ，B u 相同称为会合点或者()A u ,B
u
为边的称为会合边的两节点在e (),e ST '
e 上的投影设为。点 列，S A 1，...,A u ，B u ，，...B 1，组成初始路径。并且会合后
T K i i =+βαK e i i =++'
βαK i i >+βα，或者。若，表明双
向搜索无法会合，则搜索从当前活动点分别进行，即每一G 步搜索与GT 正向，为固定目标点或(T )GS 逆向，为固定原(S 点间夹角最小的边，直到搜索到或得到两条路径)T S,P 1正(向，)P 2逆向，取()P=min(P 1, P 2为所求解初始路径。计算初)始路径的长度，设为。
L 步：6令、分别为两棵二叉树的根节点，分别从正S T S(向、逆向出发，进行与直线段)T()ST 、TS 左右两侧各一条夹角最小的边的搜寻，把搜索到的边加入对应的二叉树，对二叉树的活动节点作步所述的两个标记。然后，从搜索到的4边的活动点出发，进行活动点与止点正向，止点始终为目(标点；逆向，止点始终为原点之间直线段左右两侧各一条)夹角最小的边的搜寻，把搜索到的边加入对应的二叉树，对K i i =+βα二叉树的活动节点作两个标记。以此类推，直至 会合于点或会合于边，生成两棵特殊的
失去的金铃子
() ()二叉树。在生成二叉树的过程中，利用步和步中的方6-16-2法可以降低二叉树的规模。
步：6-1若当前活动点是相应的方向搜索已访问过的点，则不把活动点加入相应的二叉树。若活动点的第一标记值小于已访问点的第一标记值，则活动点的父节点作为已访问点的父节点，并相应地改变已访问点的所有子节点的第一标记值。
步：6-2如果活动点的第一标记值与活动点至点正向T()或逆向的直线段距离之和大于，则在二叉树中删去活动S()L 点及其相关联的边。
步：7当时，会合点处两个第一标记的和，
其最小值会合点多于个时记为路径长度(2)r 1。当
时，会合边两端点的第一标记之和加上 e |e 其最小值会合边多于条时记为|,(2)r 2。计算r=min(r 1,r 2，为所)r 求最短路径长度。
沧州市光明小学步：8在两棵二叉树中，由会合点或会合边两端点开(e )始沿与会合点相关联的两条边或与端点相关联的边依次(e )寻求解的最短路径的节点，加入路径队列，直至达到、S ，便得到最短路径队列，终止。T 算法讨论
2.3 整个算法分为两部分，即步—步的初始解算法部分和15步—步的优化解算法部分。在初始解算法中，双向搜索每68经过一个节点只选中与两个节点间的直线段夹角最小的边，所以初始解算法搜索空间小，搜索速度快。但如果频繁地在两个相邻时刻选择的边产生左右方向的振荡，则有可能求解的最短路径大于实际最短路径，即得到一个次优解，而不是最优解。初始解只是为优化算法作准备，用于减小二叉树的规模。在优化解算法中，双向搜索在经过每个节点的同时，进行节点与或间直线段左右两侧各一条夹角最小的边的T S 1GA 搜索，例如，为当前节点，对正向搜索得到两条边，G 2
GA
)
),(min(
),(1
1
k GA
GT f GA
GT f =，且
，
)
),(min(),(2
2k GA
GT f GA GT f =f
)21(p p ，，
是
21p p ，1
1
D GA k ∈22D GA k ∈求直线夹角的函数，，，
D 1为所有和相关联且与G GT 夹角为正的边的集合，D 2为所有和相G 关联且与GT 夹角为负的边的集合。将搜索到的边分别加入两棵二叉树，随着二叉树深度的增加，相应地扩大了搜索空间，增大了双向搜索会合的概率。从搜索到的诸多路径中取距离最短的路径，便得到一个最优解。
从理论上讲，若网络节点数很少，则步中的双向搜索6可能不会合，那么从当前活动点分别进行搜索直到或。S T 但通常实际城市道路网的节点数很多，因此步中的双向搜6索容易会合。
双向搜索是从起点和终点同时搜索，在中间相遇的可能性较大。和单向搜索展开的节点数相比，双向搜索展开的节
点数至少可以减少50%
[4]
。因而算法采用双向搜索，能大大减小搜索空间，提高搜索速度。
算法分析
3 算法的分析通常以一定的模型为基础，图所示的道路1网模型的特点：结构是正方形；网络节点呈均匀分(1)(2)布，若节点数为，则和正方形四条边平行的边上的节点数
N N 为，图
。
14图道路网模型
1 显然，步、步只用常数时间。城市道路网采用邻接表14的存储方法，则步和步的时间复杂性和节点相关联的边数23成线性关系，根据矢量化的道路网的特点，通常为常数w w 且≤，因此可认为步和步只用常数时间。在图所示w 4
2
3 1 的道路网模型中，步中双向搜索会合于点或会合于边后，5N 每个方向搜索的节点数不超过，所以步的时间复杂性不 5N N 超过。在步中每个方向能会合的节点数不超过O( )6, ,
K i
i
=+βαK e i
i
=++βα而会合条件或的判断需要两重循环，所以时间复杂度不超过。步的时间复杂度和会合
O(N)7—37—
K i i =+βαK
e i i =++'βαK e
i i =++'
βα
N 的节点数呈线性关系，所以时间复杂度不超过。搜
O( )N 索会合后，二叉树的深度不超过
所以步的时间复杂度 ,8N 不超过。总之整个算法的时间复杂度不超过。O(
),O(N)算法检验4 表起点1 S 1，终点T 1的算法比较
N s ：求解过程中搜索的节点数；：求解时间，单位为秒；：求
T QL 解的最短距离，单位为米；：实际最短距离，单位为米。
RL 表起点2 S 2，终点T 2的算法比较
鲁友社区算法已用于我们研发的自主车辆导航系统，图是山东
2省济宁市道路网的一部分。矢量化的道路网的存储，主要考
虑的是车辆行驶通畅的主干路，同时为了节省存储空间，忽略了一些拥挤的小街。该图的存储共有节点个设起点253, S 1为电业局图的最左下角，终点()T 1为司法局东侧红星中路路口图的最右中侧。求解的最短路径为：正向搜索从起点向
()东，沿太白中路，经过五交化、百货大厦、济宁宾馆等节点到和浣笔泉路交叉口，然后沿着浣笔泉路向北直到核桃园路口节点；逆向搜索从终点向西，沿红星中路，经过司法局路口、保险公司路口、报社路口等节点到和浣笔泉路交叉口，然后沿着浣笔泉路向南到核桃园路口节点。再取起点S 2为图
的最左上角光河
(路和环成西路的交叉口，终点
)T 2为图的最右下角太白路和
(琵琶山路交叉口。求解的最短路径为：正向搜索从起点沿
)光河路向东，到浣笔泉路路口向南；逆向搜索从终点沿太白
路向西到浣笔泉路路口向北直到和正向搜索在红星中路路口
节点会合。算法用编制，在，内存
Vsual C++6.0PII50064MB 的计算机上运行，表、表给出本文算法和算法的比
河北理工胡佳12Dijkstra 较，显然本文算法搜索空间小、速度快、求解时间少。
结论
5 本文给出的算法适于城市道路网的最短路径寻优，道路网络越规整，算法的适用性越强。和算法相比，算Dijkstra 法不仅能得到一个最优解且搜索空间小，速度快，时间复杂度不超过。算法已经用于我们研发的自主车辆导航系O(N)统，表明算法有很高的实用价值和可靠性。
参考文献
严蔚敏，吴伟民数据结构北京：清华大学出版社1 . . ,1997
2 Fawcett J,Robinson P.Adaptive Routing for Road Traffic.IEEE Computers Graphics and Applications,2000,20(3):26-53严寒冰，刘迎春基于的城市道路网最短路径算法探讨计算
3 . GIS . 机学报，，： 200023(2) 210~215
陆汝钤人工智能北京：科学出版社，4 . . 1995
Ns
T QL RL 本文算法107 1.08 33253325
Dijkstra 算法
182
1.98
3325
N S
T QL RL 本文算法141 1.43 42804280
Dijkstra 算法
225
火星500计划2.46
4280
网聊大管家
图2 部分济宁市道路网图
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议