最短路径算法分析2

《最短路径算法分析2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、随着计算机和地理信息科学的发展,地理信息系统因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。从道路网络模型的角度看,最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径。根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。相应

2、地,最短路径问题就成为最快路径问题、最低费用问题等。因此,城市道路网作为一种大型网络设施有其本身的特征。它一方面包含网络本身的拓扑特征;另一方面还包含了大量反应地理位置特征的几何数据。本文根据道路网的特点,运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行了研究。1道路网模型及权重设置1.1道路网模型建立城市道路网主要由众多道路相交、相连构成。在纵横交织、错综复杂的道路网络中,道路间的地理位置关系相当复杂,一条道路可能与若干条道路相交相连,且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系,抽取道路网中道路交叉路口作为分析对象,并对道路

3、以交叉路口为结点进行分割,成为路段。这样,整个网络图将由交叉路口点和路段组成,并定义交叉路口点为网络的结点,路段为网络的弧。从而建立基于路段连接的网络模型,其模型形式表述为:式中,RW代表道路网络;N代表结点集;R代表路段集合,其元素为有序对,表示由结点x到结点y存在一条有向通路;LR代表路段长度集合,其元素表示有向路段的加权长度。其中,路段的加权长度是指根据目标函数要求,综合各种动态实时信息和静态属性信息后所得的路段参数,而并非真实意义下的长度。1.2道路网权重选择在交通路网中,两点间最优路径算法的优劣主要受到2个因素的影响,即所使用的最短路径算法和所选择的道路权重。最短路径算法是路径选择的

4、搜索工具,决定了如何在庞大的路网数据库中找到最佳的可行路径。道路权重则是路径选择的搜索指标,是最短路径算法的依据。因此,道路权重的选择直接影响到最优路径算法的合理性。一个城市的道路网络由不同等级的道路组成,不同等级的道路的通行能力和功能要求均不相同。只有整个城市的交通负载根据出行者目的的不同,均衡分布在不同等级的道路上,城市的路网才能得到最有效的利用。因此单纯的选择距离、时间或道路的通行能力作为道路权重都不太客观,需要选择一种比较综合的指标作为道路权重。可达性是Hansen于1959年首次提出的概念,用于定义交通网络中各结点间相互作用机会的大小。其表述的是路网中任意点之间通达的可能性及难易程度

5、,数学上指单位时间内可实现通达的直线距离[1],即为可达能力(km/m),是可达性的量度。可达性同时考虑了时间和距离的因素,把道路交通的固定设施和移动工具有机结合起来,而且避免了以道路通行能力作为权重可能造成的城市路网全局负载问题。因此以可达性为道路权重是一个比较综合的指标,具有更大的合理性。2最短路径算法最短路径问题的算法有很多种,包括基于限制条件的深度优先搜索算法、Dijkstra算法、Floyd算法、A*算法等,各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。其中,采用启发式策略的Dijkstra算法是目前公认的求解最短路问题的经典算法。但Dijkstra算法在基于网络的权矩阵

6、求解最短路问题的计算机算法和程序中,运用了关联矩阵、邻接矩阵和距离矩阵的概念。在存储图形数据和运算时,需要定义N×N的数组(其中N为网络的结点数),当网络的结点数较大时,将占有大量的计算机内存。如果不对Dijkstra算法进行优化,该算法很难在实际中得到应用。在原始的Dijkstra算法中,每次在临时标记点中搜索路径最短的结点时都要遍历所有的临时标记结点。解决办法就是将临时标记结点按照最短路径排序,每个搜索过程不必全部遍历或者较少地遍历临时标记点。或者尽量减少最短路径分析过程中搜索的临时结点数量。基于此思想,提出了以下优化算法。2.1算法原理利用两点之间直线最短的原理,在道路网中,如果两结点间

7、存在一条边,则该边为两结点间的最短路径。若不存在一条边,则连接起、止点的直线段代表了一个路线的趋势,顺着连线方向的某条边是最短路径的可能性最大。依据此思想,可以构造2个矢量,矢量一以当前结点为起点,目标点为终点;矢量二以当前结点为起点,当前结点的邻接点为终点。将矢量二的方向值与矢量一的方向值相减得到两矢量间的夹角。由夹角最小的边组成的路径最接近于最短路径。      由于只依据矢量夹角作为求解最短