随着地理信息产业的建立和数字化信息产品在全世界的普及,地理信息系统将深入到各行各业甚至各家各户,成为人们生产、生活学习和工作中不可缺少的工具和助手。 地理信息系统中网络分析功能的主要目的是对地理网络、城市基础设施网络(如交通网络、各种网线、电力线、电话线、供排水管线等)进行地理分析和模型化。 最短路径问题是地理信息系统网络分析中的最基本、最关键的问题,在交通网络结构的分析、交通运输线路的选择、通讯线路的建造与维护、运输货流的最小成本分析、城市公共交通网络的规划等,都有直接应用的价值。 关于最短路径问题,目前为人们常用的求解方法,是1959年由E.W.Dijkstar提出的标号法,但该方法在具体实现中在存储空间及运行效率上还存在着一定的问题。 本文从图形数据的存储结构及最短路径顶点的搜索策略两个方面对Dijkstra算法进行了改进,提出了一种基于矢量角度的最短路径搜索算法。该方法采用一种类似于面向对象的数据存储结构来存储网络图中的节点及弧段对象,相对于Dijkstra算法存储数据常用的邻接矩阵、邻接表等结构,节约了大量的存储空间。 在最短路径的搜索上引入矢量夹角标量值做为搜索因子,提高了最短路径搜索向终点的收敛速度;充分利用网络图中各元素间的拓扑关系,减小了每次搜索的节点范围;同时还考虑了各弧段的长度值(或权值),较好的将网络图中对象的空间信息和属性信息相结合。 经过实验,以本文讨论的算法求解最短路径得出的结果在准确性及速度方面都能满足实际要求。