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

摘要：

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

关键词：编码图、关键路径、AOE网、广度优先搜索、时间复杂度

所属期刊栏目：34

分类号：TP311.4(计算技术、计算机技术)

资助基金：粤港关键领域重点突破项目06KJcd001;深圳职业技术学院科技基金资助项目03KJc054

在线出版日期：2008-07-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：106-108