一种求解关键路径的新算法

• 作者: 王明福
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 编码图 关键路径 AOE网 广度优先搜索 时间复杂度
• 年，卷（期）: 2008,（9）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 106-108
• 页数: 3页
• 分类号: TP311.4
• 字数: 4222字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2008.09.038

摘要

通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法.该算法扩充图的邻接表的存储结构,使图的存储与算法求解过程共享同一存储空间.从图的源节点开始,用加权取极大运算规则,广度优先递归对图中所有节点进行编码.编码图生成后,利用反向搜索求出从源点到汇点的所有关键路径及长度.该算法比现有算法更简单直观,所需的存储空间更小,算法时间复杂度降低到O(n+e),优于现有算法的O(n2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王明福	深圳职业技术学院软件工程系	24	134	7.0	10.0