最短路径问题是网络分析中的一个重要问题，求解该问题的方法有很多，目前公认的、较优的求解方法是著名的算法。

该算法是基于图论中的网络模型，在求解时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 NetBI Jun 1，FU Mengyin 1，ZHOU Peide 2，ZHANG Yuhe 1；(1.Department of Automatic Control, Beijing Institute of Technology2.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 the 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 Engineering2002年12月 December 2002· 博士论文·中图分类号： TP301.6文章编号：1000—3428(2002)12 —0036—03文献标识码：A—36—NextWeightPositionNamePositionWeightNext算法实现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 ,Bu为边的称为会合边的两节点在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经过一个节点只选中与两个节点间的直线段夹角最小的边，所以初始解算法搜索空间小，搜索速度快。

但如果频繁地在两个相邻时刻选择的边产生左右方向的振荡，则有可能求解的最短路径大于实际最短路径，即得到一个次优解，而不是最优解。

初始解只是为优化算法作准备，用于减小二叉树的规模。