基于道路网的最短路径算法的研究与实现

地理信息系统(GIS)是以地理空间数据库为基础,采用地理模型分析方法,适时提供多种空间和动态的地理信息,为地理研究和地理决策服务的强有力的工具。随着计算机及网络的普及和发展,GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。最短路径问题是网络分析中最基本的问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。最短路径分析在车辆导航系统以及各种城市应急系统中有着广泛的应用。 本文介绍了有关地理信息系统的一些基本概念,包括地理信息系统概念、地理信息系统的发展及现状、地理信息系统的应用领域、地理信息系统数据模型、地理信息系统数据的组织和管理、地理信息系统中的网络分析,简述了地理信息系统应用软件MapInfo的特点。 针对城市交通道路网的特点,对基于城市道路网的最短路径分析的关键技术进行了研究和分析,着重分析研究了城市交通道路网的矢量地图表达、网络拓扑结构的提取和构建、最短路径算法的高效实现等关键技术。 最短路径问题是交通网络分析中的一个重要问题,也是交通地理信息系统(GIS-T)中的一个研究热点。它是资源分配、路线设计及分析等优化问题的基础。本文根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种基于椭圆限制区域的优化二叉堆优先级队列的改进型Dijkstra最短路径算法。此算法是在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起点、中间点以及终点,设定合理的椭圆限制搜索区域,以减少算法的搜索规模;并且利用两点间直线段最短的原理,以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。该算法能够有效降低Dijkstra算法的时间复杂性,提高系统的运行效率。 在系统实现部分,利用MapBasic语言,在MapInfo平台上实现了最短路径分析,可通过简单的点击操作,确定起点、中间点和终点,得到最短路径并予以显示,方便直观。