2
$\begingroup$

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?

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 14 '16 at 6:09
  • $\begingroup$ " There are lower bounds for the shortest path (i.e., k=1), which are not linear." -- That's patently false for the unweighted case. $\endgroup$ – Raphael Jul 14 '16 at 6:09
  • $\begingroup$ @Raphael you are right, I was thinking about the weighted case. $\endgroup$ – Rostov Jul 15 '16 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.