关键路径的稀疏矩阵求解算法  

Sparse matrix algorithm to solve the critical path

作　　者：张春生[1] 

机构地区：[1]内蒙古民族大学数学与计算机科学学院 内蒙古通辽028043

出　　处：《计算机应用》2006年第3期529-530,共2页journal of Computer Applications

基　　金：内蒙古高校科学研究项目(NJ03169)

摘　　要：求解AOE网的关键路径算法一般基于拓扑排序,虽然具有较好的时间复杂度(O(n+e)),但由于必须进行拓扑排序,同时还要进行拓扑逆序扫描,使得算法本身比较复杂。针对这个问题提出了一个算法,算法采用了稀疏矩阵作为数据的存储结构,为防止关键路径丢失,采用队列方式进行操作。同经典算法相比,该算法简单,时间复杂度相近(O(n+e2/n))。The algorithm to solve the critical path of the AOE net is generally based on the topological sort. Although this algorithm has good asymptotic time complexity （ O（n ＋ e ） ）, it is comparatively complex because the topological sort and the topological inverted sequence scanning must be carried on. An algorithm was proposed, using sparse matrix as the storage structure of the data. To prevent the critical path from being lost, the queue method was adopted for the operation. Compared with the classical algorithm, this algorithm is simple, with close asymptotic time complexity （ O （n ＋ e^2/n ） ）.

关 键 词：AOE网 关键路径 稀疏矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]