RANKED K-LONGEST PATHS IN AN ACYCLIC NETWORK, ITS ALGORITHM AND APPLICATION

Abstract

The acyclic network on which our problem is defined is a weighted directed graph G=(N, A) with no directed cycle. A method to determine the first, second, third, .. , and k-th longest paths for a given integer
k ~2 is described. An algorithm of O(k2m) to determine the k-longest path in the network consisting of m arcs is also given. There can be various advantages of determining k-longest path in many industrial, engineering and management problems that deal with planning and scheduling of activities involvingn specified jobs subjected to precedence constraints. Indeed, such problems can be.modelled
mathematically by acyclic networks