A Shortest Path Algorithm on Multi-stage Weighted Network with Quadratic Parameter
带二次参数赋权的多阶段网络最短路算法

The static network shortest path algorithms have been developed thoroughly,whereas the studies for dynamic network shortest path algorithms are few.To satisfy the need of theoretical research and application,the dynamic network shortest path problems have been a hot spot in the field of geographic information science and computer science.When the weights of the network are functions with parameter,the network is called a dynamic network,in which it is difficult to resolve shortest path by the traditional algorithms.In this paper,we first propose the shortest path problem in a multi-stage weighted network with quadratic parameter.Next,we give the implicit enumerative labelling algorithm to look for the shortest path of this network based on the thought of the Dijkstra algorithm and the implicit enumerative method.Finally,we analyse the complexity of the algorithm.The theory analysis and the experiment indicate that the algorithm is not polynomial but effective for proper scale of the network.