Narrow Results

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$(k_1(nm+log{k}_1))$ time method to compute paths without repeat nodes and to answer the next question: how many paths $k_1$ 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 $k_1$ remains as an open problem.

Given an undirected graph $G=(V,E)$ with a weight function $c\in R^E$, and a positive integer $K$, the Kth Traveling Salesman Problem (Kth TSP) is to find $K$ Hamilton cycles $H_1,H_2,\dots ,H_K$ such that, for any Hamilton cycle $H\notin \{H_1,H_2,\dots ,H_K\}$, we have $c(H)\ge c(H_i),i=1,2,\dots ,K$. This problem is NP-hard even for $K$ fixed. We prove that Kth TSP is pseudopolynomial when TSP is polynomial.