Ranking One Million Simple Paths in Road Networks.

In this paper, we address the problem of finding the best paths connecting a given pair of nodes in a directed graph with arbitrary lengths. We introduce an algorithm to determine the best paths in order of length when repeat nodes in the paths are allowed. We obtain an O time and O space algorithm to implicitly determine the shortest paths in a directed graph with nodes and 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 time method to compute paths without repeat nodes and to answer the next question: how many paths in practice are needed to identify simple paths using the previous algorithm? We find that the response is usually O based on an experiment computing one million paths in USA road networks. The determination of a theoretical tight bound on remains as an open problem. [ABSTRACT FROM AUTHOR]