北京东方首选教育企业集团（管理顾问有限公司）

引言随着计算机技术以及地理信息科学的发展,GIS(地理信息系统)[1]的空间分析功能得到越来越广泛的应用。网络分析作为空间分析的方法之一,在许多领域中发挥着重要的作用,而网络分析中最基本最关键的问题就是最短路径问题,人们在继D ijkstra算法之后,又进行了大量的研究工作,提出了大量求解最短路径的算法[2-8]。并且有不少学者提出了适用于GIS的最短路径算法[9-10]。然而这些研究都是针对固定拓扑和固定权值的网络,没有考虑拓扑结构随时间变化、权值是时间函数等的时变情况。GIS网络是一种时变网络,网络的拓扑结构、各边的权值都随时间变化而变化。许多学者都认识到以固定拓扑为基础的网络理论不能适应于GIS网络。目前已有不少学者开始研究时变拓扑网络中的最短路径问题[11]。1传统的D ijkstra算法1.1算法原理网络图中的结点分为未标记结点、临时标记结点和永久标记结点三种类型。初始化时所有的结点都置为未标记结点,在搜索过程中凡是与最短路径中的结点相连通的结点都是临时标记结点,把从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点。