An algorithm for calculating k shortest paths with a maximum number of arcs

In multiexchange telecommunication networks the problem of calculating shortest paths involves, in general, constraints on the maximum number of arcs in any path. In highly connected networks the number of available paths between pairs of nodes is very high and if no additional constraints are introduced, shortest paths (for a given objective function) may occur having a significant number of arcs. In this paper we present an efficient algorithm for calculating the k shortest loopless paths with a maximum number of arcs per path, derived from the MPS algorithm for calculating the k shortest loopless paths. The proposed algorithm will be compared with the original MPS algorithm when both procedures are used for enumerating the k shortest loopless paths with a maximum number of arcs, in order to show the significant efficiency improvement obtained from the algorithm. The comparison will be made in terms of the total number of generated paths in each algorithm. This is a corrected version of an earlier paper (IAOR abstract 78809).