9
$\begingroup$

I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map):

  • positively weighted
  • undirected
  • sparse
  • with about 100 nodes

My current plan is to apply $k$ shortest path routing to each pair; I am now looking for a more efficient alternative (possibly with dynamic programming).

$\endgroup$
  • 3
    $\begingroup$ Honestly, for 100 vertices, it seems unlikely that you need anything more efficient than solving each of the 45,000 pairwise problems. $\endgroup$ – David Richerby Aug 8 '16 at 8:08
6
$\begingroup$

First of all, a crucial difference in computing $k$-shortest paths is if the paths need to be simple or not. A path is called simple, if it does not contain nodes repeatedly. A path with a loop, for example, is not simple. Note that on the Wikipedia page you linked, the articles are concerned with not necessarily simple paths. The case of simple paths seems to be harder than the case with not necessarily simple paths.

The all-pairs $k$-shortest simple paths problem

This seems to be a quite young area of research. A recent paper by Agarwal and Ramachandran can be found on the ArXiv [1]. The previous-work section will also give you some insight into the history of the problem.

The all-pairs $k$-shortest paths problem

Here, indeed, it is the best choice to just repeatedly apply Eppsteins algorithm [2]. The general observation that a repeated application of an algorithm for the single-source version of the problem is the fastest approach was already made in 1977 by E. L. Lawler [3]; Eppstein provides the fastest algorithm to date for this subproblem.

References

[1] Agarwal, U. and Ramachandran, V. Finding $k$ Simple Shortest Paths and Cycles. arXiv:1512.02157 [cs.DS] https://arxiv.org/pdf/1512.02157.pdf

[2] Eppstein, D. Finding the k shortest paths. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, E. L. Comment on a computing the k shortest paths in a graph. Communications of the ACM, 20(8):603–605, 1977.

$\endgroup$
  • $\begingroup$ Thank you. Since I am working with subway map, I need them to be simple path (it doesn't make sense for my software to guide people to go back and forth), so I guess I would just go with Yan's algorithm. $\endgroup$ – Franklin Yu Aug 8 '16 at 16:22
  • $\begingroup$ Interesting and quite surprising that apparently 10,000 cases of a problem can't be solved faster than just solving 10,000 single cases, one after the other. $\endgroup$ – gnasher729 Aug 9 '16 at 14:08
  • $\begingroup$ the idea of paths with loops included in the "shortest paths" seems counterintuitive & unusual because there is seemingly an equivalent "path" with the loop removed, and one also wonders if these can be efficiently constructed from the simple paths etc... $\endgroup$ – vzn Aug 11 '16 at 22:39

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.