A minimum incoming weight label method and its application in CPM networks

E Munapo, BC Jones, S Kumar


An efficient approach towards finding a directed, shortest path or a directed longest path from the source to all other nodes in a directed network is described in this paper. Application of this approach with respect to CPM project networks is also considered. The approach is based on a minimum incoming weight labelling method and determines a critical path for a given project activity network. Although many algorithms exist in the operational research literature that may be used to find critical paths, the method discussed in this paper has an interesting application in determining optimal crash limits for various activities in a CPM network. In case of network topology changes due to any reason, such as that an activity has to be completed in crash duration or the actual duration of an activity takes longer than scheduled, a new critical path and new associated floats can be computed without analyzing the complete network all over again. This is achieved by recycling part of the available information. The algorithm presented in this paper is illustrated by means of numerical examples.

Full Text:


DOI: https://doi.org/10.5784/24-1-58


  • There are currently no refbacks.

ISSN 2224-0004 (online); ISSN 0259-191X (print)

Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help