摘要
当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的.
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 imphcit 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 hut effective for proper scale of the network.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2007年第7期92-97,共6页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(10471081)
山西省自然科学基金(2007011043)
关键词
多阶段网络
二次参数
最短路
临界点
标号算法
multi-stage network
quadratic parameter
the shortest path
critical point
labelling algorithm
