DFSCRIP: An implementation of a single-pass algorithm for the critical path method

Abstract

Scope and Method of Study: The scope of this report is the development of comparable computer programs for a new single-pass algorithm and the conventional method for finding the critical path in a project network and to study their relative efficiencies. Adequate examples are used for being able to draw conclusions about the complexities of the algorithms. Since the nature of the study is theoretical, the examples used are arbitrary networks and not drawn from real life situations.

Conclusions: The results of the computer executions indicated that the complexity of the new algorithm is linear, requiring time proportional to the number of activities in the network. However, the algorithm turned out to be slower than expected and was only marginally faster than the conventional algorithm. The storage requirements of the two algorithms were also proportional to the number of activities, but the new algorithm needed somewhat more storage. These results led to the conclusion that both the algorithms are of approximately equal overall efficiencies.