一种求解DGA图中具有长度约束的简单路径问题算法

• 作者: 何建军
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: 有向无环图 简单路径 长度约束
• 年，卷（期）: 2019,（10）
• 所属期刊栏目: 算法与语言
• 页码范围: 82-85
• 页数: 4页
• 分类号: TP312
• 字数: 4555字
• 语种: 中文
• DOI: 10.11907/rjdk.182897

摘要

具有长度约束的简单路径问题具有较高的应用价值.在一般图中,它是一个NP完全问题,除非NP=P,否则没有多项式时间算法.而对于一些特殊的图,如有向无环图,可以找到多项式时间算法.因此对有向无环图中具有长度约束的简单路径问题进行研究.首先根据有向无环图的特点,建立递归方程,然后根据递归方程给出一个在有向无环图中求解具有长度约束的简单路径问题算法,同时给出一个有向无环图中具有长度约束的简单路径构造算法.为证明算法正确性,进行相应实例验证,把求解该问题的时间复杂度由O(N×T×L)改进为O((N+|E|)L),空间复杂度改进为O(|E|+N).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何建军	广东科技学院计算机学院	1	0	0.0	0.0