带二次参数赋权的多阶段网络最短路算法

当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的.

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.