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

最短路径分析是GIS网络分析的基础。传统的最短路径算法中，比较经典的算法是Dijkstra算法。由于地理信息系统中的数据具有不确定性、数据量庞大等特点，因此采用传统的Dijkstra算法进行最短路径分析就不适应。为此本文分析了传统网络中的最短路径算法-Dijkstra算法在时变权值网络结构中的局限性，给出了一种适应于时变权值网络的最短路径算法，并且利用改进的邻接表作为存储结构对算法进行了优化。

A Shortest Path Algorithm for GIS Time-varying Weight Networks

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.