系统管理学报 ›› 2017, Vol. 26 ›› Issue (2): 252-258.
• 运筹学与工业工程 • 上一篇 下一篇
摘要: 针对如何在无回路有向连通图中求解 阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径。在该思路的指引下,提出了新的参数概念,如点参数 、弧参数 、以及终点的特征参数 ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数 定理和弧参数 定理;利用这些参数和定理,设计出在无回路有向连通图中求解 阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为 , 表示弧数;最后,通过应用举例对该算法进行了演示。
苏志雄,乞建勋,魏汉英. 求解无回路有向连通图中的k阶最短路径问题[J]. 系统管理学报, 2017, 26(2): 252-258.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: https://xtglxb.sjtu.edu.cn/CN/
https://xtglxb.sjtu.edu.cn/CN/Y2017/V26/I2/252