GIS时变权值网络最短路径算法研究  

A Shortest Path Algorithm for GIS Time-varying Weight Networks

作　　者：胡腾波[1] 叶建栲[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《计算机与现代化》2008年第11期22-24,共3页Computer and Modernization

摘　　要：最短路径分析是GIS网络分析的基础。传统的最短路径算法中,比较经典的算法是Dijkstra算法。由于地理信息系统中的数据具有不确定性、数据量庞大等特点,因此采用传统的Dijkstra算法进行最短路径分析就不适应。为此本文分析了传统网络中的最短路径算法-Dijkstra算法在时变权值网络结构中的局限性,给出了一种适应于时变权值网络的最短路径算法,并且利用改进的邻接表作为存储结构对算法进行了优化。Time-varying weight network is different from classical fixed weight networks and also different from time-dependent networks which have been studied. Shortest path analysis is the basis of network analysis in GIS. In classical shortest path algo- rithm, the more classical is Dijkstra algorithm. Because datum is uncertain and huge in GIS, it is unsuitable to use classical Dijk- stra algorithm to analyze shortest path. This paper proves that the shortest path algorithm of classical fixed weight networks--Dijk- stra algorithm is restrictive in time-varying weight networks. Here, a shortest path algorithm for time-varying weight networks is given. Further more, by using an improved adjacency-list as structure, this algorithm is optimized, and improvement in complexity of algorithms is achieved.

关 键 词：GIS 不确定性 时变权值网络 邻接表 最短路径算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]