Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Question

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t,ドル the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?

Answer 1

No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers

• Raphael: Welcome to Computer Science! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here.
• Raphael: " There are lower bounds for the shortest path (i.e., k=1), which are not linear." -- That's patently false for the unweighted case.
• Rostov: @Raphael you are right, I was thinking about the weighted case.