摘要
针对如何在无回路有向连通图中求解k阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径。在该思路的指引下,提出了新的参数概念,如点参数N、弧参数A以及终点的特征参数θ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数N定理和弧参数A定理;利用这些参数和定理,设计出在无回路有向连通图中求解k阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为O(km),m表示弧数;最后,通过应用举例对该算法进行了演示。
For the kth shortest path problem in the connected digraph without loop, we propose a new idea that the path can be obtained by computing difference between the lengths of the path and the shortest path. With this idea, we define the parameters such as node parameter N, arc parameter A and trait parameter θ of the terminal node, and propose the formula for calculating them. We then find the relations between the parameters and corresponding paths in the graph, and derive the theorems for node parameter N and arc parameter A. We design a polynomial algorithm for the kth shortest path problem based on above results, and prove correctness of the algorithm. The complexity of the algorithm is O（krn） where m is the number of arcs. We also demonstrate the algorithm by an example.
出处
《系统管理学报》
CSSCI
CSCD
北大核心
2017年第2期252-258,共7页
Journal of Systems & Management
基金
国家自然科学基金资助项目(71171079)
江西省高校人文社会科学项目(GL1591)
关键词
运筹学
k阶最短路
点参数N
弧参数A
特征参数θ
optimization algorithm
kth shortest path
node parameter
arc parameter
trait parameter
