欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
针对如何在无回路有向连通图中求解忌阶最短路问题，提出了新的思路，即先求出某路径与最短路的长度之差，再利用该差值求得该路径。在该思路的指引下，提出了新的参数概念，如点参数N、弧参数A以及终点的特征参数θ，并给出了这些参数的计算方法；揭示了这些参数与图中相应路径之间的关系，推导出点参数N定理和弧参数A定理；利用这些参数和定理，设计出在无回路有向连通图中求解k阶最短路问题的多项式算法，证明了算法的正确性，并且经过分析，该算法的复杂度为0（kin），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.
同期刊论文项目
同项目期刊论文
Reformulations and Efficient Computation for Project Portfolio Selection Problem Considering Project
Expanded model of the project portfolio selection problem with divisibility, time profile factors an
GA optimization model for discrete time/cost trade-off problem in repetitive projects considering re
期刊信息
位置：