第25卷 第6期2005年11月
长安大学学报(自然科学版)
Journal of Chang πan University (Natural Science Edition )
Vol. 25 No. 6
Nov. 2005
文章编号:167128879(2005) 0620062204
城市道路最短路径的Dijkst ra 算法优化
张渭军1, 王 华2
(1. 长安大学地球科学与国土资源学院, 陕西西安710054; 2. 陕西交通职业技术学院经济管理系, 陕西西安,710021)
摘 要:在研究城市道路网络特征基础上, 建立城市道路网络模型及其数据库, Dijkst ra 算法对城市道路进行最短路径查询, 和终点到起点的方向进行搜索23s , 改进算法时间为0. 20s 。Dijkst ra 算法的O (2) n , , 是一种寻求最优路径的有效算法。关键词:ra 算法; 最短路径; 二叉树中图分类号:U491.1 文献标识码:A
Optimination Dijkstra arithmetic for shortest p ath of urb an traffic net
ZHAN G Wei 2jun 1, WAN G Hua 2
(1. School of Earth Sciences and Resources Management , Chang ’an University , Xi ’an 710054,China ; 2. Depertmeat of Economy and Management , Shaanxi College of C ommunications T echnology , Xi ’an 710021,China )
Abstract :This paper established t he road net model and database of urban traffic based on t he st udy of t he urban t raffic road character. The shortest pat h was queried by t he improving Dijkst ra arit hmetic , t he arit hmetic used B 2t ree in t he start and end point separately in t he direction of start 2end and end 2start. The times are 0. 20s and 0. 23s when using Optimination Dijkstra arit h 2metic and t he Dijkstra arit hmetic. The simulation result s indicate t hat t he complex grade in time is minished to O (n ) f rom t he Dijkst ra ’s O (n 2) , t he shortest pat h is agreed wit h t he practice , t he arit hmetic is an effective met hod in selecting t he shortest pat h. 2tabs , 1fig , 7ref s.
K ey w ords :t raffic engineering ; road net ; datebase ; Dijkstra arit hmetic ; shortes ’pat h ; B 2t ree
0 引 言
交通网络分析是指通过一定方法, 评价网络特征的区位特征及特征之间的相互关系, 分析个体在交通网络中一定时间内可能的活动范围。交通网络分析的重点是路径分析, 而路径分析的核心为最优路径[1], 以最短路径为主的最优路径是交通工程学、
收稿日期:2004211209
基金项目:国家自然科学基金项目(60072044)
地理信息科学研究的一个热点, 它往往是建立在抽象的数学模型即网络模型的基础上, 该模型中最短路径分析就是在指定网络两节点间找一个阻碍强度最小的路径, 它不仅包括距离最短还可以引伸到其他变量如时间、费用、线路容量等。本文在对城市交通网络进行一定数学抽象的基础上, 建立了一个基于地理相对关系的数学模型, 提出求城市道路网络
作者简介:张渭军(19752) , 男, 陕西渭南人, 长安大学讲师, 博士研究生.
第6期 张渭军, 等:城市道路最短路径的Dijkst ra 算法优化最短路径的Dijkst ra 改进算法, 该算法的时间复杂度为O (n ) , 通过实际检验, 其结果更符合实际。
63
实体抽象为网络图论理论中的网络图, 然后在此模型基础上建立相应的属性数据库, 本文数据在Map 2Info 环境中进行矢量化, 共分2个图层:节点图层及
1 建立模型及属性数据库
城市交通主要由众多的街道相交、相连而构成, 并组成纵横交错、错综复杂的城市交通网络图[2]。本文以交叉路口点把道路进行分割, 这样整个交通网将由交叉路口点和路段组成, 并定义交叉路口点为网络的节点, 路段为网络的边。建立模型过程就是把现实中的城市道路网络实体抽象为网络图论理论中的网络图, 这就要理解它们二者的不同之处, 然后通过一定的综合变换把它们有机地对应起来, 城市网络图最大特点有以下几个方面:
(1) 城市交通特征的空间分布存在显著的方向性差异, 力、[3], , 而交叉口之间的路段被抽象为网络图中带权弧, 它具有不同的通行能力、交通流量和阻抗。
(2) 在公路路网分析规划或交通规划研究中, 交叉口仅作为路的交叉点或控制段的结点来考虑, 其长度等几何要素也要记入里程, 相对而言, 交叉口的宽度属于比较次要的位置。但对城市公交来说, 交叉口宽度占所有道路的5%以上, 这样交叉口宽度就不能忽略。交通流在交叉口处有不同程度的延误, 这对最短路径查询有影响, 同时由于城市的历史变迁并不规整, 许多交叉口是多路或畸形交叉, 所以在GIS (地理信息系统) 中对城市道路基础图的修正与编辑关键为交叉口定义图形编辑原则。在此主要考虑3种情况:①2条路的十字交叉, 这样在交叉口的中心断开; ②2条路的T 型交叉, 同样也是在交叉口断开; ③多路或畸形交叉, 这要根据实际情况进行处理, 必需反映到模型中去。
(3) 拓扑关系的表达, 在传统平面模型中, 道路之间的拓扑关系通过弧段节点属性表的方式隐式表达, 交叉的道路在交叉口分享节点, 这是一种典型几何拓扑表达[4]。网络拓扑与几何拓扑并不是总是一致的, 对于具有社会属性的交通网络而言, 部分拓扑是人为设定的, 如转向限制、转向阻抗等, 网络拓扑中的转向限制主要通过平面拓扑转向表的方式来表达, 实际建模过程, 转向没有阻抗的可以删去, 以节省存储空间。
针对以上城市交通网络特点, 把城市道路网络
道路图层, 每个图层有其对应的属性表结构, 属性表结构文件定义了空间对象的属性数据的表结构。因此, 在节点图层和道路图层的属性表结构文件中定义的节点和道路信息见表1、表2。
表1 路段结点属性表
节点代码
NodeID
节点名称
NodeName
节点行车方向
NodeDirection
换车时间
Change Time
表2 路段信息属性表
路段名称
路段等级
Road Gra
RoadCw
路段起点
RoadF
路段终点
RoadE
在3. M IF 文件中主要包含了空间数据[5], 指明了地图的坐标系、属性表结构、地图对象的类型和地理坐标信息等, 对图层中每一路段, 均记录了该路段的起点和终点经纬度坐标。因此, 可以直接对3. M IF 文件进行操作, 从中提取各节点的坐标信息,
表2中有路段起点、终点, 这样表1、表2的属性表就建立了联系。
2 最短路径计算
城市道路网模型为G =(V , E ) 。其中,V 为站点综合后产生的节点集合; E 为相邻两节点的距离即弧段距离, 它是1个非负实数。
) }E ={d ab |d ab =F (X 1, X 2, X 3…
(1)
式中:X 1为简单距离因子, 表示道路几何距离; X 2为路面等级因子; X 3为拥挤程度因子。
X 2、X 3表示路面等级和人、车流量等因素对通
行能力的影响, 可以使用阻抗值来表示这种影响程度, 而阻抗值的大小就需对整个交通区内路段等级和拥挤程度进行分类, 然后依次对每一类赋予阻抗值。这样, 阻抗值的大小表示路段等级和拥挤程度等对通行能力的影响, 虽然这种影响只是定性的, 并不能如实表示影响的大小, 但却具有横向的比较性。2. 1 Dijkstra 最短路径算法
Dijkst ra 算法的基本思路是:假如每点都有一
对标号(d j , p j ) , 其中d j 是从起源点s 到点j 的最短路径的长度(从1个点到其本身的长度为0, 2个互不相通的点的距离为无穷大) , p j 则是从s 到j 的最
64
长安大学学报(自然科学版) 2005年
边, 设该边的另一端点分别为A 1和B 1即
|f (sj sA 1|=min (|f (sj sA i |)
i ∈D 1
短路径中j 点的前一点, 求解从起源点s 到j 的最短路径算法基本过程为:
(1) 初始化, 起始点设置为:①d s =0, p s 为空; ②所有其他点:d t =∞, 对不同的点寻找最短路径时, p t 不同; ③标记起源点s , 记k =s , 其他所有点设置为未标记的。
(2) 检查从所有已标记的点k 到其直接连接的
其中, D 1为所有与s 相连的节点数;
|f (js jB 1|=min (|f (js jB i |)
i ∈D 2
其中, D 2为所有与t 相连的节点数。
如果A 1是从s 出发所选的点, 则把A 1当作当前点, 用该步骤寻找以A 1为起点且与A 1j 的最小的边, 如此反复直至当前所选的点与j 点重合, 这样得到的一个链为最短路径的一个解。当所选点为终止点并该点与j 不重合时, 则这一条链到此结束, 然后把所选点的前一个点当作当前点继续, 。j 出发的另一s 。这样s j 之间的2条、1条, 并记录该链。该步骤所得的最短路径具有s j 两点的方向性趋势, 但其条件简单因此需进一步检验。
(3) 同样以s 、j 分别为根结点, 然后分别用二叉树从s 、j 出发, 重复将s 、j 直线段两侧夹角最小的边加入二叉树, 对该二叉树的活动节点作2个标记, 直至与j 或s 点重合。这样s j 之间的最短路径最多有4条结果。为了减少花费时间并使构造的二叉树最
未标记的点j 的距离, 并设置
(2) d j =min {d j , d k +l kj }
式中:l kj 为从k 到j 的直接连接距离。
(3) 选取下一个点, 从所有未标记的结点中, 选取d j 中最小的一个i 值
d i =min {d j , 所有未标记的点j}
对应点i 最短路径中的1点, 并设为已标定的。
(4) 找到点i 的前一点, 接连接点i 的点i =u
(5) 标记点i , , 则算法退出, 否则记k =i , 转到式(2) 再继续。
由上可知, 顶点越多, 循环次数越多, 计算时间将成倍增长。Dijkstra 算法所采用的图遍历是以顶点数为基数作二次循环[6], 每重循环的次数均为节点数n , 它的执行过程产生了以s 为节点的一棵树, 随着算法的进一步执行该树向四面八方延伸, 直至到达终点为止, 其算法执行的时间复杂度为O (n 2) , 它可以寻找出从源点s 到所有节点的最短路径。显然, 从最终结果来看, 有些分支对最短路径的求得无益, 能否删除这些分支, 从而减少计算最短路径的时间, 这正是本文提出改进Dijkst ra 算法的原因。2. 2 Dijkstra 算法改进
同上, 设s 和j 是网络中任意给定的2个节点, 要寻找s 到j 的最优路径, 该路径是由边和节点组成的, 一般交通网络中, 组成s j 的各段道路都和s j 在同一条方向上是最简单的一种情况, 而多数情况下组成s j 最优路径的节点和s j 边不在1条直线上, 但其大致方向应是从s 指向j 。在此把最短路径分解为多个子问题进行求解, 即由s 到j 和由j 到s 2个方向的最短路径。:
(1) 计算s j 的直线距离k =s j 若s j 之间存在1条边, 则该边为最短路径, 若s j 上存在1条边链即s j 由在一个方向的几条路段组成, 则该边链和为最短路径, 并记录该链所经过的站点及总距离, 否则, 执行步骤(2) 。
(2) 分别从s 、j 出发, 寻找与s j j 小, 应采用两种方法:首先对于二叉树的遍历采用广
度优先的方法, 尽可能减少二叉树的节点遍历数; 其次对于子结点在加入路径队列前, 对其进行判断, 如果为终点j (s ) , 则不加入路径队列, 但要对其影响的节点和子节点累加长度标志进行改变。
通过上述算法之后, 最多可能得到4条最短路径, 并把各路径的阻抗值显示出来, 然后通过人工对比, 最终选1条最优路径。
3 算法效率比较
基于邻接矩阵的传统Dijkst ra 算法, 时间复杂度为O (n 2) , 即使改用邻接表存储网络数据结构, 虽然大大改进算法的空间复杂度, 但对事件时间复杂度丝毫没有改善[7]。当节点数目较大时, 算法的时间花费极为庞大。本文的算法复杂度为O (n ) , 它与节点数呈线性关系, 当节点数大时, 其优势就更加明显。为了验证本文算法的有效性, 以西安城区为例(图1) , 在Map Info 环境下对地图进行矢量化, 然后再在VB 环境下通过对Map X 二次开发, 实现了最短路径的快速搜索。图中共有交叉路口538个, 计算机配置为Pentium Ⅲ550, 内存为128M , 硬盘
第6期 张渭军, 等:城市道路最短路径的Dijkst ra 算法优化为10G , 用Dijkstra 算法, 时间为0. 23s , 用改进算法时间为0. 20s , 并且它选了4条最短路径及各条路径的阻抗, 由用户比较这几条路径长度及其阻抗, 从中选出1条最优路径, 这比单纯的距离最短更符合实际。图中黑粗线即为起始站点到终点的最优路径, 列表框内显示的是该线路所经过的站点, 当交叉路口多时该算法时间效果更为明显
。
参考文献:R eferences :
65
[1] 李英姿, 张飞舟, 林耀海. 智能交通系统中地理信息系
统的研究[J].中国公路学报,2000,13(3) :97-100.
L I Y ing 2zi , ZHAN G Fei 2zhou , L IN Yao 2hai. Research on geographic information system in intelligent trans 2portation systems [J].China Journal of Highway and Transport ,2000, 13(3) :97-100.
[2] 桂 岚, 李跃军. 组件式交通地理信息系统设计与开发
[J].长安大学学报(自然科学版) ,2002,22(2) :24-27.
GU I Lan , L I Yue 2jun. and development of a [J ].Journal of Edition ) , 2002, ], 晏克菲. 城市道路网络交通特性仿真模型及最
短路径算法[J].交通运输工程学报,2002,2(3) :60-62.
ZHAN G Guo 2qiang , YAN Ke 2fei. Simulation model based upon characteristics of urban road network and its shortest path algorithm[J].Journal of Traffic and
图1 本文算法查询最短路径结果
Transportation Engineering ,2002,2(3) :60-62. [4] 严寒冰, 刘迎春. 基于GIS 的城市道路网最短路径算法
该算法查找两点之间最短路径出现4条, 最终
从中选距离是48. 8km , 阻抗为35的1条路为最优路径。当不计阻抗只按距离来讲, 当然选距离为47. 9km 的1条路为最短路径, 很显然前一种更符合人们的思维习惯。
探讨[J].计算机学报,2000,23(2) :210-215.
Y AN Han 2bing , L IU Y ing 2chun. A new algorithm for finding shortcut in a city ’s road net based on GIS technol 2ogy[J].Chinese J Computers , 2000,23(2) :210-215. [5] 吴必军, 李利新, 雷小平. 基于城市道路数据库的最短路
4 结 语
(1) 最短路径是GIS 网络分析在交通上最重
径搜索[J].西南交通大学学报,2003,38(1) :80-83.
WU Bi 2jun , L I Li 2xin , L EI Xiao 2ping. Shortest path searching based on city road database [J].Journal of Southwest Jiaotong University , 2003,38(1) :80-83. [6] 周培德. 交通道路网中任意两点之间最短路径的快速
要、最基本的应用, 以往最短路径搜寻都是基于几何
距离的最短路径, 它对于公路交通而言更具意义, 但对城市道路而言, 距离最短不一定最优, 因为还有路面等级和拥挤程度等因素的影响。
(2) 本文最短路径搜索是从起点和终点分别用二叉树按其方向性进行搜索, 用Dijkstra 算法, 时间为0. 23s , 用改进算法时间为0. 20s , 改进Dijkst ra 算法的效率明显比传统的Dijkst ra 算法效率高, 并且搜索结果更符合实际。
(3) 须改进的地方是在计算道路阻抗时要考虑更多的影响因子, 这有待进一步研究。
算法[J].计算机工程与科学,2002,24(2) :35-37.
ZHOU Pei 2de. A fast algorithm for finding the shor 2test path between arbitrary two points in a traffic road net [J].Computer Engineering and Science , 2002, 24(2) :35-37.
[7] 刘灿齐, 杨佩昆. 基于最短路径的城市干道网规划的算
法研究[J].中国公路学报,2000,13(2) :105-107.
L IU Can 2qi , YAN G Pei 2kun. Urban main road network planning algorithm on shortest 2path[J].China Journal of Highway and Transport ,2000,13(2) :105-107.
第25卷 第6期2005年11月
长安大学学报(自然科学版)
Journal of Chang πan University (Natural Science Edition )
Vol. 25 No. 6
Nov. 2005
文章编号:167128879(2005) 0620062204
城市道路最短路径的Dijkst ra 算法优化
张渭军1, 王 华2
(1. 长安大学地球科学与国土资源学院, 陕西西安710054; 2. 陕西交通职业技术学院经济管理系, 陕西西安,710021)
摘 要:在研究城市道路网络特征基础上, 建立城市道路网络模型及其数据库, Dijkst ra 算法对城市道路进行最短路径查询, 和终点到起点的方向进行搜索23s , 改进算法时间为0. 20s 。Dijkst ra 算法的O (2) n , , 是一种寻求最优路径的有效算法。关键词:ra 算法; 最短路径; 二叉树中图分类号:U491.1 文献标识码:A
Optimination Dijkstra arithmetic for shortest p ath of urb an traffic net
ZHAN G Wei 2jun 1, WAN G Hua 2
(1. School of Earth Sciences and Resources Management , Chang ’an University , Xi ’an 710054,China ; 2. Depertmeat of Economy and Management , Shaanxi College of C ommunications T echnology , Xi ’an 710021,China )
Abstract :This paper established t he road net model and database of urban traffic based on t he st udy of t he urban t raffic road character. The shortest pat h was queried by t he improving Dijkst ra arit hmetic , t he arit hmetic used B 2t ree in t he start and end point separately in t he direction of start 2end and end 2start. The times are 0. 20s and 0. 23s when using Optimination Dijkstra arit h 2metic and t he Dijkstra arit hmetic. The simulation result s indicate t hat t he complex grade in time is minished to O (n ) f rom t he Dijkst ra ’s O (n 2) , t he shortest pat h is agreed wit h t he practice , t he arit hmetic is an effective met hod in selecting t he shortest pat h. 2tabs , 1fig , 7ref s.
K ey w ords :t raffic engineering ; road net ; datebase ; Dijkstra arit hmetic ; shortes ’pat h ; B 2t ree
0 引 言
交通网络分析是指通过一定方法, 评价网络特征的区位特征及特征之间的相互关系, 分析个体在交通网络中一定时间内可能的活动范围。交通网络分析的重点是路径分析, 而路径分析的核心为最优路径[1], 以最短路径为主的最优路径是交通工程学、
收稿日期:2004211209
基金项目:国家自然科学基金项目(60072044)
地理信息科学研究的一个热点, 它往往是建立在抽象的数学模型即网络模型的基础上, 该模型中最短路径分析就是在指定网络两节点间找一个阻碍强度最小的路径, 它不仅包括距离最短还可以引伸到其他变量如时间、费用、线路容量等。本文在对城市交通网络进行一定数学抽象的基础上, 建立了一个基于地理相对关系的数学模型, 提出求城市道路网络
作者简介:张渭军(19752) , 男, 陕西渭南人, 长安大学讲师, 博士研究生.
第6期 张渭军, 等:城市道路最短路径的Dijkst ra 算法优化最短路径的Dijkst ra 改进算法, 该算法的时间复杂度为O (n ) , 通过实际检验, 其结果更符合实际。
63
实体抽象为网络图论理论中的网络图, 然后在此模型基础上建立相应的属性数据库, 本文数据在Map 2Info 环境中进行矢量化, 共分2个图层:节点图层及
1 建立模型及属性数据库
城市交通主要由众多的街道相交、相连而构成, 并组成纵横交错、错综复杂的城市交通网络图[2]。本文以交叉路口点把道路进行分割, 这样整个交通网将由交叉路口点和路段组成, 并定义交叉路口点为网络的节点, 路段为网络的边。建立模型过程就是把现实中的城市道路网络实体抽象为网络图论理论中的网络图, 这就要理解它们二者的不同之处, 然后通过一定的综合变换把它们有机地对应起来, 城市网络图最大特点有以下几个方面:
(1) 城市交通特征的空间分布存在显著的方向性差异, 力、[3], , 而交叉口之间的路段被抽象为网络图中带权弧, 它具有不同的通行能力、交通流量和阻抗。
(2) 在公路路网分析规划或交通规划研究中, 交叉口仅作为路的交叉点或控制段的结点来考虑, 其长度等几何要素也要记入里程, 相对而言, 交叉口的宽度属于比较次要的位置。但对城市公交来说, 交叉口宽度占所有道路的5%以上, 这样交叉口宽度就不能忽略。交通流在交叉口处有不同程度的延误, 这对最短路径查询有影响, 同时由于城市的历史变迁并不规整, 许多交叉口是多路或畸形交叉, 所以在GIS (地理信息系统) 中对城市道路基础图的修正与编辑关键为交叉口定义图形编辑原则。在此主要考虑3种情况:①2条路的十字交叉, 这样在交叉口的中心断开; ②2条路的T 型交叉, 同样也是在交叉口断开; ③多路或畸形交叉, 这要根据实际情况进行处理, 必需反映到模型中去。
(3) 拓扑关系的表达, 在传统平面模型中, 道路之间的拓扑关系通过弧段节点属性表的方式隐式表达, 交叉的道路在交叉口分享节点, 这是一种典型几何拓扑表达[4]。网络拓扑与几何拓扑并不是总是一致的, 对于具有社会属性的交通网络而言, 部分拓扑是人为设定的, 如转向限制、转向阻抗等, 网络拓扑中的转向限制主要通过平面拓扑转向表的方式来表达, 实际建模过程, 转向没有阻抗的可以删去, 以节省存储空间。
针对以上城市交通网络特点, 把城市道路网络
道路图层, 每个图层有其对应的属性表结构, 属性表结构文件定义了空间对象的属性数据的表结构。因此, 在节点图层和道路图层的属性表结构文件中定义的节点和道路信息见表1、表2。
表1 路段结点属性表
节点代码
NodeID
节点名称
NodeName
节点行车方向
NodeDirection
换车时间
Change Time
表2 路段信息属性表
路段名称
路段等级
Road Gra
RoadCw
路段起点
RoadF
路段终点
RoadE
在3. M IF 文件中主要包含了空间数据[5], 指明了地图的坐标系、属性表结构、地图对象的类型和地理坐标信息等, 对图层中每一路段, 均记录了该路段的起点和终点经纬度坐标。因此, 可以直接对3. M IF 文件进行操作, 从中提取各节点的坐标信息,
表2中有路段起点、终点, 这样表1、表2的属性表就建立了联系。
2 最短路径计算
城市道路网模型为G =(V , E ) 。其中,V 为站点综合后产生的节点集合; E 为相邻两节点的距离即弧段距离, 它是1个非负实数。
) }E ={d ab |d ab =F (X 1, X 2, X 3…
(1)
式中:X 1为简单距离因子, 表示道路几何距离; X 2为路面等级因子; X 3为拥挤程度因子。
X 2、X 3表示路面等级和人、车流量等因素对通
行能力的影响, 可以使用阻抗值来表示这种影响程度, 而阻抗值的大小就需对整个交通区内路段等级和拥挤程度进行分类, 然后依次对每一类赋予阻抗值。这样, 阻抗值的大小表示路段等级和拥挤程度等对通行能力的影响, 虽然这种影响只是定性的, 并不能如实表示影响的大小, 但却具有横向的比较性。2. 1 Dijkstra 最短路径算法
Dijkst ra 算法的基本思路是:假如每点都有一
对标号(d j , p j ) , 其中d j 是从起源点s 到点j 的最短路径的长度(从1个点到其本身的长度为0, 2个互不相通的点的距离为无穷大) , p j 则是从s 到j 的最
64
长安大学学报(自然科学版) 2005年
边, 设该边的另一端点分别为A 1和B 1即
|f (sj sA 1|=min (|f (sj sA i |)
i ∈D 1
短路径中j 点的前一点, 求解从起源点s 到j 的最短路径算法基本过程为:
(1) 初始化, 起始点设置为:①d s =0, p s 为空; ②所有其他点:d t =∞, 对不同的点寻找最短路径时, p t 不同; ③标记起源点s , 记k =s , 其他所有点设置为未标记的。
(2) 检查从所有已标记的点k 到其直接连接的
其中, D 1为所有与s 相连的节点数;
|f (js jB 1|=min (|f (js jB i |)
i ∈D 2
其中, D 2为所有与t 相连的节点数。
如果A 1是从s 出发所选的点, 则把A 1当作当前点, 用该步骤寻找以A 1为起点且与A 1j 的最小的边, 如此反复直至当前所选的点与j 点重合, 这样得到的一个链为最短路径的一个解。当所选点为终止点并该点与j 不重合时, 则这一条链到此结束, 然后把所选点的前一个点当作当前点继续, 。j 出发的另一s 。这样s j 之间的2条、1条, 并记录该链。该步骤所得的最短路径具有s j 两点的方向性趋势, 但其条件简单因此需进一步检验。
(3) 同样以s 、j 分别为根结点, 然后分别用二叉树从s 、j 出发, 重复将s 、j 直线段两侧夹角最小的边加入二叉树, 对该二叉树的活动节点作2个标记, 直至与j 或s 点重合。这样s j 之间的最短路径最多有4条结果。为了减少花费时间并使构造的二叉树最
未标记的点j 的距离, 并设置
(2) d j =min {d j , d k +l kj }
式中:l kj 为从k 到j 的直接连接距离。
(3) 选取下一个点, 从所有未标记的结点中, 选取d j 中最小的一个i 值
d i =min {d j , 所有未标记的点j}
对应点i 最短路径中的1点, 并设为已标定的。
(4) 找到点i 的前一点, 接连接点i 的点i =u
(5) 标记点i , , 则算法退出, 否则记k =i , 转到式(2) 再继续。
由上可知, 顶点越多, 循环次数越多, 计算时间将成倍增长。Dijkstra 算法所采用的图遍历是以顶点数为基数作二次循环[6], 每重循环的次数均为节点数n , 它的执行过程产生了以s 为节点的一棵树, 随着算法的进一步执行该树向四面八方延伸, 直至到达终点为止, 其算法执行的时间复杂度为O (n 2) , 它可以寻找出从源点s 到所有节点的最短路径。显然, 从最终结果来看, 有些分支对最短路径的求得无益, 能否删除这些分支, 从而减少计算最短路径的时间, 这正是本文提出改进Dijkst ra 算法的原因。2. 2 Dijkstra 算法改进
同上, 设s 和j 是网络中任意给定的2个节点, 要寻找s 到j 的最优路径, 该路径是由边和节点组成的, 一般交通网络中, 组成s j 的各段道路都和s j 在同一条方向上是最简单的一种情况, 而多数情况下组成s j 最优路径的节点和s j 边不在1条直线上, 但其大致方向应是从s 指向j 。在此把最短路径分解为多个子问题进行求解, 即由s 到j 和由j 到s 2个方向的最短路径。:
(1) 计算s j 的直线距离k =s j 若s j 之间存在1条边, 则该边为最短路径, 若s j 上存在1条边链即s j 由在一个方向的几条路段组成, 则该边链和为最短路径, 并记录该链所经过的站点及总距离, 否则, 执行步骤(2) 。
(2) 分别从s 、j 出发, 寻找与s j j 小, 应采用两种方法:首先对于二叉树的遍历采用广
度优先的方法, 尽可能减少二叉树的节点遍历数; 其次对于子结点在加入路径队列前, 对其进行判断, 如果为终点j (s ) , 则不加入路径队列, 但要对其影响的节点和子节点累加长度标志进行改变。
通过上述算法之后, 最多可能得到4条最短路径, 并把各路径的阻抗值显示出来, 然后通过人工对比, 最终选1条最优路径。
3 算法效率比较
基于邻接矩阵的传统Dijkst ra 算法, 时间复杂度为O (n 2) , 即使改用邻接表存储网络数据结构, 虽然大大改进算法的空间复杂度, 但对事件时间复杂度丝毫没有改善[7]。当节点数目较大时, 算法的时间花费极为庞大。本文的算法复杂度为O (n ) , 它与节点数呈线性关系, 当节点数大时, 其优势就更加明显。为了验证本文算法的有效性, 以西安城区为例(图1) , 在Map Info 环境下对地图进行矢量化, 然后再在VB 环境下通过对Map X 二次开发, 实现了最短路径的快速搜索。图中共有交叉路口538个, 计算机配置为Pentium Ⅲ550, 内存为128M , 硬盘
第6期 张渭军, 等:城市道路最短路径的Dijkst ra 算法优化为10G , 用Dijkstra 算法, 时间为0. 23s , 用改进算法时间为0. 20s , 并且它选了4条最短路径及各条路径的阻抗, 由用户比较这几条路径长度及其阻抗, 从中选出1条最优路径, 这比单纯的距离最短更符合实际。图中黑粗线即为起始站点到终点的最优路径, 列表框内显示的是该线路所经过的站点, 当交叉路口多时该算法时间效果更为明显
。
参考文献:R eferences :
65
[1] 李英姿, 张飞舟, 林耀海. 智能交通系统中地理信息系
统的研究[J].中国公路学报,2000,13(3) :97-100.
L I Y ing 2zi , ZHAN G Fei 2zhou , L IN Yao 2hai. Research on geographic information system in intelligent trans 2portation systems [J].China Journal of Highway and Transport ,2000, 13(3) :97-100.
[2] 桂 岚, 李跃军. 组件式交通地理信息系统设计与开发
[J].长安大学学报(自然科学版) ,2002,22(2) :24-27.
GU I Lan , L I Yue 2jun. and development of a [J ].Journal of Edition ) , 2002, ], 晏克菲. 城市道路网络交通特性仿真模型及最
短路径算法[J].交通运输工程学报,2002,2(3) :60-62.
ZHAN G Guo 2qiang , YAN Ke 2fei. Simulation model based upon characteristics of urban road network and its shortest path algorithm[J].Journal of Traffic and
图1 本文算法查询最短路径结果
Transportation Engineering ,2002,2(3) :60-62. [4] 严寒冰, 刘迎春. 基于GIS 的城市道路网最短路径算法
该算法查找两点之间最短路径出现4条, 最终
从中选距离是48. 8km , 阻抗为35的1条路为最优路径。当不计阻抗只按距离来讲, 当然选距离为47. 9km 的1条路为最短路径, 很显然前一种更符合人们的思维习惯。
探讨[J].计算机学报,2000,23(2) :210-215.
Y AN Han 2bing , L IU Y ing 2chun. A new algorithm for finding shortcut in a city ’s road net based on GIS technol 2ogy[J].Chinese J Computers , 2000,23(2) :210-215. [5] 吴必军, 李利新, 雷小平. 基于城市道路数据库的最短路
4 结 语
(1) 最短路径是GIS 网络分析在交通上最重
径搜索[J].西南交通大学学报,2003,38(1) :80-83.
WU Bi 2jun , L I Li 2xin , L EI Xiao 2ping. Shortest path searching based on city road database [J].Journal of Southwest Jiaotong University , 2003,38(1) :80-83. [6] 周培德. 交通道路网中任意两点之间最短路径的快速
要、最基本的应用, 以往最短路径搜寻都是基于几何
距离的最短路径, 它对于公路交通而言更具意义, 但对城市道路而言, 距离最短不一定最优, 因为还有路面等级和拥挤程度等因素的影响。
(2) 本文最短路径搜索是从起点和终点分别用二叉树按其方向性进行搜索, 用Dijkstra 算法, 时间为0. 23s , 用改进算法时间为0. 20s , 改进Dijkst ra 算法的效率明显比传统的Dijkst ra 算法效率高, 并且搜索结果更符合实际。
(3) 须改进的地方是在计算道路阻抗时要考虑更多的影响因子, 这有待进一步研究。
算法[J].计算机工程与科学,2002,24(2) :35-37.
ZHOU Pei 2de. A fast algorithm for finding the shor 2test path between arbitrary two points in a traffic road net [J].Computer Engineering and Science , 2002, 24(2) :35-37.
[7] 刘灿齐, 杨佩昆. 基于最短路径的城市干道网规划的算
法研究[J].中国公路学报,2000,13(2) :105-107.
L IU Can 2qi , YAN G Pei 2kun. Urban main road network planning algorithm on shortest 2path[J].China Journal of Highway and Transport ,2000,13(2) :105-107.