A Shortest Path Algorithm for GIS Time-varying Weight Networks
YE Jian-kao · Computer and Modernization · 2008
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 algorithm,the more classical is Dijkstra algorithm.Because datum is uncertain and huge in GIS,it is unsuitable to use classical Dijkstra algorithm to analyze shortest path.This paper proves that the shortest path algorithm of classical fixed weight networks—Dijkstra 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.