An algorithm for ranking paths that may contain cycles (Q759658)

An algorithm is presented for determining the K best paths that may contain cycles in a directed network. The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed. The proposed algorithm can be used not only for the classical K shortest paths problems but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists. Computational results are presented and comparisons with other approaches for the classical problem are made.