Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

Question

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).

Answer 1

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.