Ranking One Million Simple Paths in Road Networks
Abstract
In this paper, we address the problem of finding the K best paths connecting a given pair of nodes in a directed graph with arbitrary lengths. We introduce an algorithm to determine the K best paths in order of length when repeat nodes in the paths are allowed. We obtain an O(m+nlogn+K(n+logK)) time and O(K+m) space algorithm to implicitly determine the K shortest paths in a directed graph with n nodes and m arcs. Empirical results where the algorithm was used to compute one hundred million paths in USA road networks are reported. A non-trivial modification of the previous algorithm is performed obtaining an O(k1(nm+logk1)) time method to compute paths without repeat nodes and to answer the next question: how many paths k1 in practice are needed to identify K simple paths using the previous algorithm? We find that the response is usually O(K) based on an experiment computing one million paths in USA road networks. The determination of a theoretical tight bound on k1 remains as an open problem.