Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.

► We study the K best paths computation, between two nodes in acyclic graphs. ► The method is based on representing each kth shortest simple path by a tree. ► The algorithm runs in O(m + k(n + log K)) time and O(K + m) space, in DAGs with n nodes and m arcs. ► Tests show the algorithm performs well, compared to previous literature.