最短路径算法分析

随着计数机和地理信息科学的发展，地理信息系统因其强大的功能得到日益广泛和深入的应用，网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通信等各种管网、管线的布局设计中发挥了重要的作用，通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题，它作为许多领域中选择最优问题的基础，在应急救援指挥系统中占有重要地位。

　 　 从道路网络模型的角度看，最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径，根据阻碍强度的不同定义，最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、路线容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。因此，城市道路网作为一种大型网络设施尤其本身的特征。它一方面包含网络本身的拓扑特征，另一方面还包含了大量反应地理位置特征的几何数据。因此，运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行分析。

1、道路网模型建立

   城市道路网主要由众多道路相交、相连构成。在纵横交织、错综复杂的道路网络中，道路间的地理位置关系相当复杂，一条道路可能与若干条道路相交相连，且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系，抽取道路网中道路交叉路口作为分析对象，并对道路以交叉口为结点进行分割，成为路段。这样，整个网络图将由交叉路口点和路段组成，并定义交叉路口为网络的结点，路段为网络的弧。从而建立基于路段连接的网络模型，其模型形式表述为：{Rw=(N,R,LR)

{R={(x,y)|x,y∈N,且L(x,y)}

{LR={lxy|(x,y)∈R}

式中，Rw代表道路网络；Ｎ代表结点集；Ｒ代表路段集合，其元素为有序对(x,y)，L(x,y)表示由结点x到结点y存在一条有向通路；LR代表路段长度集合，其元素lxy表示有向路段(x,y)的加权长度。其中，路段的加权长度是指根据目标函数要求，综合各种动态实时信息和静态属性信息后所得的路段参数，而并非真实意义下的长度。

2.道路网权重选择

   在交通路网中，两点间最优路径算法的优劣主要受到两个因素的影响，即所使用的最短路径算法和所选择的道路权重。最短路径算法是路径选择的搜索工具，决定了如何在庞大的路网数据库中找到最佳的可行路径。道路权重则是路径选择的搜索指标，是最短路径算法的依据。因此，道路权重的选择直接影响到最优路径算法的合理性。

   道路网络由不同等级的道路组成，不同等级的道路的通行能力和功能要求均不相同。因此单纯地选择距离、时间或道路的通行能力作为道路权重都不太客观，需要选择一种比较综合的指标作为道路权重。

3.最短路径算法

最短路径问题的算法有很多种，包括基于条件的深度优先搜索算法、Dijkstra算法、Floyd算法、A*算法等，各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。其中，采用启发式策略的Dijkstra算法是目前公认的求解最短路径问题的经典算法。但Dijkstra算法在基于网络的权矩阵求解最短路径问题的计数机算法和程序中，运用了关联矩阵、邻接矩阵的概念。在存储图形数据和运算时，需要定义ＮｘＮ的数组（其中Ｎ为网络的结点数），当网络的结点数较大时，将占有大量的计数机内存，因此，需要对Dijkstra算法进行优化。