求解无回路有向连通图中的k阶最短路问题

• 作者: 乞建勋 苏志雄 魏汉英
• 来源期刊: 系统管理学报
• 学科: 数学
• 关键词: 运筹学 k阶最短路 点参数N 弧参数A 特征参数θ
• 年，卷（期）: 2017,（2）
• 页码范围: 252-258
• 页数: 7页
• 分类号: O221
• 语种: 中文

摘要

针对如何在无回路有向连通图中求解k阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径.在该思路的指引下,提出了新的参数概念,如点参数N、弧参数A以及终点的特征参数θ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数N定理和弧参数A定理;利用这些参数和定理,设计出在无回路有向连通图中求解k阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为O(km),m表示弧数;最后,通过应用举例对该算法进行了演示.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	乞建勋	华北电力大学经济与管理学院	148	2350	27.0	41.0
2	苏志雄	南昌工程学院工商管理学院	13	25	3.0	4.0
3	魏汉英	南昌工程学院工商管理学院	8	5	1.0	1.0