交通网络中最短路径算法的研究

随着计算机及网络的普及和发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。最短路径问题是网络分析中最基本的问题，它作为许多领域中选择最优问题的基础，在交通网络分析系统中占有重要地位。最短路径分析在汽车导航系统以及各种城市应急系统中有着广泛的应用。 本文简述了有关地理信息系统的一些基本概念，包括地理信息系统概念、地理信息系统数据模型、地理信息系统数据的组织和管理、地理信息系统中的网络分析，概述了地理信息系统的发展和应用状况。 针对城市交通道路网的特点，对基于城市道路网的最短路径分析的关键技术进行了研究和分析，着重分析研究了城市交通道路网的矢量地图表达、网络拓扑结构的提取和构建、最短路径算法的高效实现等关键技术。 根据GIS中网络计算的实际情况，从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手，提出了一种基于椭圆限制区域的优化二叉堆优先级队列的改进型Dijkstra最短路径算法。此算法是在对城市交通网络空间分布特征进行统计分析的基础上，针对具体的起、终节点，设定合理的椭圆限制搜索区域，以减少算法的搜索规模；并且利用两点间直线段最短的原理，以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。该算法能够有效降低Dijkstra算法的时间复杂性，提高系统的运行效率。实际应用表明，该方法兼具灵活性和实用性能够满足求解交通网络最短路径的要求，并能够延伸到其它管网如电力和光缆等的维护和抢修等应用领域。