基于动态规划思想求解关键路径的算法

Algorithm for finding the critical paths based on dynamic programming

关键路径通常是在拓扑排序的基础上求得的。提出了一种利用图的广度优先搜索与动态规划算法相结合求解关键路径的新算法,该算法采用图的邻接表结构形式,不需要进行拓扑排序,较传统的算法具有较高的效率,同时具有较高的健壮性。

Critical paths are usually obtained by topological collating. A new algorithm for finding critical path by using dynamic programming and breadth-first search was put forward. The data structure of the algorithm is adjacency lists, and it doesnt need topological sorting. This algorithm with higher efficiency than traditional ones, and also with higher healthy.