城市道路最短路径算法的研究收稿日期:2006-02-23基金项目:吉林省交通厅资助项目(040123)作者简介:杨天石(1973-),男(汉),湖南岳阳,工程师主要研究测绘工程与G IS 的工程。
杨天石1,刘晓东2,于小平3(1.中国有色金属工业长沙勘察设计研究院,长沙410011;21长春工程学院勘查与测绘工程学院,长春130021;31吉林大学地探学院,长春130026)摘 要:建立城市公交最短路径有利于城市交通建设有序和稳定的发展,目前采用GIS 技术可以有效地管理公交车辆。
从系统的最短路径入手,对行走路线作了分析,并给出了用于空间分析的最短路径追踪方法。
此外介绍了该系统在具体城市交通应用中所要遵循的原则。
关键词:最短路径;Dijkstra 算法;GIS ;MapObject 中图分类号:P208文献标识码:A 文章编号:100928984(2006)022*******0 引言城市道路是城市的重要基础设施,它的运行的直接影响着城市的规划、建设和管理。
面对未来的城市,道路有效地运行,无疑是城市发展的一个重要方面。
城市交通担负着客流传输、能源输送等工作,也是城市赖以生存和发展的物质基础。
但由于多方面的原因,造成在运行时利用不高,我国现有公路网络的运行不是令人满意的。
另一方面,我国现有的公路资料都以图纸、图表等形式记录保存,采用人工方式管理,效率低下,资料系统性差。
对于变化的区域,数据维护困难,各部门也存在为了建设方便重复收集资料,标准不统一,管理混乱等情况。
而城市道路做为地面工程规划设计、施工和运行管理的基础数据,必须为合理地开发利用道路,加强城市道路的统一规划管理提供科学依据。
鉴于以上情况,必须建立城市道路数据库与信息系统,利用竣工测量,实现动态更新,为城市规划与建设管理提供高精度、高可靠性、现势性的城市道路数据信息;同时充分利用系统提供道路的一系列空间分析和道路辅助设计功能。
这将大大提高道路信息的社会和经济效益。
1 道路系统的模型框架城市道路信息系统是利用地理信息系统技术、现代关系数据库、网络技术、多媒体技术和其它专业技术,采集、管理、更新与处理城市道路信息的,具有空间决策支持和专家系统综合分析能力的综合性信息系统。
同一般的地理信息系统相比,具有道路数据的网络性和连通性特点,这是系统的重要环节,所以在道路数据的更新与分析中建立道路的拓扑关系显得尤为重要。
1.1 系统数据加工MapObject 所采用的是shape 格式的数据,而shape 不能支持拓扑,直接实现算法比较困难。
这里就需要自己建立拓扑关系,达到网络分析的目的。
步骤如下:(1)在ArcMap 中编辑所需要的数据层(如:线层,这里为“中心线”),在Editor 菜单下的Options 中的T opology 的属性页中选择好适当的ClusterT oler 2ance 值,然后对整幅图进行Integrate ,确保所有的线没有拓扑错误。
在ArcCatalog 里将刚才所编辑的shape 文件转换成C overage 格式,打开该文件的C ov 2erage Properties ,用Build 建立好Node 。
(2)用ArcMap 打开建立好拓朴后的C overage 数据的Arc 和Node 层,并分别将其导成一个线状的和一个点状的Shape 文件,分别取名为line.shp 和node.shp 。
1.2 数据模型建立11211 构建矩阵定义3个数组,分别存放相应Arc 的起点、终点 ISS N 100928984C N 2221323/N长春工程学院学报(自然科学版)2006年第7卷第2期J.Changchun Inst.T ech.(Nat.Sci.Edi.),2006,V ol.7,N o.219/2857259和长度(fnode、tnode、length),对这些数组进行初始化,读出所有Arc的这些信息,分别对应的属性字段为:Fnode 、Tnode 、length 。
在初始化过程中,把Arc 的Fid作为数组的下标。
定义一个数组dist,用来存放对应点到起点的最短路径长度,下标同样为Arc的Fid。
并对其初始化,使每个的值都赋为无穷大,程序中采用的是1E +30。
定义一个布尔型的数组Finished,用来记录结点是否被遍历。
下标用Arc的Fid。
初始化Finished,使每个值都为False。
定义一个数组PreP oint,记录每一点到起点的最短路径的前一点。
11212 找出对应的起始点找起始点时,从Node层中用鼠标点出一点,查出该点的“中心线 ”字段(如果在建拓扑时所用的层名字是其它,此属性就会有不同的名字,如C overage 层名字为“道路中心线”时,此字段便是“道路中心线 ”),此属性值对应的便是Arc的一个起点或终点。
确定终点的方法一样。
这里,把确定起点的值定为S,终点的值定为E。
11213 遍历所有结点标记起点已遍历,Finished(S)=true。
查找所有以S为起点和终点的Arc,把该Arc对应的终点和起点存到另一个数组NodeC onnected中去。
使dist(s)=0,比较dist(NodeC onnected)与dist(s)+ length(NodeC onnected)的大小,如果dist(Nodeconnect2 ed)>dist(s)+length(nodeconnected)时,使dist(node2 connected)=dist(s)+length(nodeconnected),使Pre2 P oint(nodeconnected)=s。
将nodeconnected中没有标记为已遍历的结点作为起点,重复以上步骤。
11214 表示出最短路径从E点开始,查找的PreP oint(E),此点为最短路径路线的终点的前一点,找出该点的前一点Pre2 P oint(PreP oint(e)),直到起点为止,这些结点所经过的路线便是所求的最短路径,而最短路径长度为dist(E)。
11215 输出结果在最短路径的结点中,找出所有以相邻的两点为起点和终点的Arc,并高亮显示,并输出dist(E)的值。
2 对Dijkstra算法的改进Dijkstra算法是最初产生的从S到它自身的路径,这条路径没有边,其长度为0。
在Dijkstra算法的每一步中,产生下一个最短路径。
一种方法是在目前已产生的最短路径中加入一条可行的最短的边,结果产生的新路径是原先产生的最短路径加上一条边。
这种策略并不总是起作用。
另一种方法是在目前产生的每一条最短路径中,考虑加入一条最短的边,再从所有这些边中先选择最短的。
它可以验证按长度顺序产生最短路径时,下一条最短路径总是由一条已产生的最短路径加上一条边形成。
实际上,下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的,且这条路径所到达的顶点其最短路径还未产生。
第二条路径是第一条路径扩充一条边形成的;第三条路径则是第二条路径扩充一条边;第四条路径是第一条路径扩充一条边;第五条路径是第三条路径扩充一条边。
通过上述观察可用一种简便的方法来存储最短路径。
可以利用数组p,p[i]给出从s到达i的路径中顶点i前面的那个顶点。
在本例中p[1:5]= [0,1,2,3,4]。
从s到顶点i的路径可反向创建。
从i出发按p[i],p[p[i]],p[p[p[i]]],…的顺序,直到到达顶点s或0。
在本例中,如果从i=5开始,则顶点序列为p[i]=4,p[4]=3,p[3]=1=s,因此路径为1,3,4,5。
为能方便地按长度递增的顺序产生最短路径,定义d[i]为在已产生的最短路径中加入一最短边的长度,从而使得扩充的路径到达顶点i。
最初,仅有从s到s的一条长度为0的路径,这时对于每个顶点i,d[i]等于a[s][i](a是有向图的长度邻接矩阵)。
为产生下一条路径,需要选择还未产生最短路径的下一个节点,在这些节点中d值最小的即为下一条路径的终点。
当获得一条新的最短路径后,由于新的最短路径可能会产生更小的d值,因此有些顶点的d值可能会发生变化。
将与s邻接的所有顶点的p初始化为s,这个初始化用于记录当前可用的最好信息。
也就是说,从s到i的最短路径,即是由s到它自身那条路径再扩充一条边得到。
当找到更短的路径时,p[i]值将被更新。
若产生了下一条最短路径,需要根据路径的扩充边来更新d的值。
步骤如下:(1)初始化d[i]=a[s][i](1≤i≤n),对于邻接于s的所有顶点i,置p[i]=s,对于其余的顶点置p[i]=0;对于p[i]≠0的所有顶点建立L表。
(2)若L为空,终止,否则转至3。
(3)从L中删除d值最小的顶点。
(4)对于与i邻接的所有还未到达的顶点j,更新d[j]值为min{d[j],d[i]+a[i][j]};若d[j]发85长春工程学院学报(自然科学版)2006,7(2)生了变化且j还未在L中,则置p[j]=1,并将j加入L,转至2。
3 应用实例系统开发环境为Visual Basic+MapObjects2.1。
公交查询系统总共实现了站点、线路的双向查询,两地之间的路线换乘查询这些功能。
数据准备,为实现这些功能,准备了两个数据层,分别为公交的线路层(Bus Line)和公交站点层(BusNode),在Bus Line层中建立起Line属性字段,用来记录经过此线路的车次,之间用逗号隔开,如:,14路,19路,22路,64路。
在BusNode层中也建立起Line属性字段,用来记录经过点站点的公交车次,之间用逗号隔开,如:,10路,11路,1路,2路,6路,6-28路,18路,25路,61路,62路。
双向查询,这里的双向查询的原理同一般的双向查询功能实现一样。
公交换乘查询,主体思路:此算法分为一次查找(直接查找)、二次查找(以经过起点的线路的其它路点为起点,原来终点以终点进行直接查找)和三次查找(以经过起点的线路的其它站点为起点,经过终点的线路的其它站点为终点进行直接查找)这3种,没有更多地进行是因为考虑到现实情况之中的情况,在换乘较多次数时将会失去他本身的意义,故只作了3次查找。
4 结论本文从空间分析的角度出发,较详细地研究了网络分析中最短路径问题,以及在最短路径基础上的公共交通信息查询。
尤其是采用图的结点、弧段联合结构表示公共交通线路网络中的相互关系,建立了网络要素之间的拓扑结构,从而较方便地查询交通信息及最短路径。
在Dijkstra算法的基础上,采用邻接点算法来优化最短路径问题,在一定程度上节省了存贮空间和提高了运算速度。
用较好的数式来组织公共汽车车次和站点数据,在算法上能实现n次转车情况,并比较出最佳乘车方案。
参考文献[1] W ANG Jie2chen,M AO Hai2cheng,Y ANG De2zhi.Unitedstructure of point-arc for netw ork graph and it’s applicationin GISs shortest path searching[J].Acta G eodaetica et Acr2 tographica S inica,2000,29(1):1—5.[2] M O Zhong2xi.A new alg orithm for finding shortest path tree[J],Journal of Mathimatics,1995,15(1):57—62.[3] S ONGJu2chuan,LI Jun,ZH ANG Wen2jun.Alg orithm on howto find the shortest path in GIS[J].Journal of Shanghai Uni2 versity(Natural Science),1997,15(3):61—64.[4] Shaffer C A.Data structures and alg orithm analysis[M].Bei2jing:Prentice Press,1998.[5] LU K ai2cheng,LU Hua2ming.G raphic theory and its applica2tion[M].Beijing:Tsinghua University Press,1995.[6] BI AN Fu2ling.The Principle and Method of GIS[M].Beijing:Surveying and Mapping Press,1996.1—8.R esearch on arithmetic for the shortestpath of urban traffic netY ANG T ian2shi,et al.(China Nonferrous Metal Industry Changsha Survey andDesign Research Institute,Changsha410011,China) Abstract:Building the shortest path of urban traffic net is benefit to the stable development of urban communica2 tions.Nowadays,bus rapid transit vehicles are managed efficiently by using GIS.This paper analyzes vehicle route begin with the shortest path and gives tracing method for the shortest path using for spatial analysis.As well as the principles obeyed when the system is used in the urban traffic net are introduced.K ey w ords:shortest path;Dijkstra arithmetic;GIS;Map Object95杨天石,等:城市道路最短路径算法的研究。