# Which k-best shortest-path algorithms should I consider?

I'm solving a graph-search optimization problem. I need to find the k best acyclic shortest-paths through a directed weighted graph.

I know there are a number of exact and approximate k-best algorithms, but most of the recent research seems to be oriented toward very large, very sparsely-connected graphs (e.g. road routing and directions), and my graph is neither.

Distinguishing aspects of my problem:

• The graph consists of approximately 160 vertices.

• The graph is nearly fully connected (bidirectionally, so ~160^2 ~= 25k edges)

• k will be quite small (probably less than 10)

• The maximum path length will probably be bounded and very small as well (e.g. 3-5 edges)

• I said 'acyclic' above, but just to reiterate - solutions must not include cycles. This isn't an issue for 1-best shortest path, but it becomes a problem for k-best - for example, consider a road routing - the 2nd shortest path from A to B might be the same as the 1-best, with a quick trip around a block somewhere. That's might be mathematically optimal, but not a very useful solution. ;-)

• We may need to re-weight edges on-the-fly for each calculation. An edge cost consists of a weighted sum of several factors, and the final requirements (whenever we get them) may allow a user to specify their own prioritization of those weighting factors, altering edge weights. This is a relatively small graph (we should be able to represent it in a few hundred KB), so it's probably reasonable to clone the graph in memory, apply the re-weighting, and then execute the search on the cloned graph. But if there's a more effective method of performing the search while computing weights on-the-fly, I'm interested.

I'm looking at the algorithms described in Santos (K shortest path algorithms), Eppstein 1997 (Finding the k Shortest Paths), and others. Yen's algorithm is of interest, primarily because of the existing Java implementation. I'm not scared to read the research papers, but I thought it was worth throwing out the details of my problem and asking for pointers to save some reading time.

And if you have pointers to Java implementations, even better.

• +1, because I'm interested in the suggestions people have, and this seems like the exact type of question this site was made for. Jan 9, 2013 at 14:54
• Doesn't your acyclic condition means that ANY other path from from start to goal would create cycle with the first path? And if both start and goal are in blind alley, every path must use these two edges. Jan 9, 2013 at 16:04
• Maybe I wasn't clear. The acyclic constraint applies only to a single path - naturally, any 2 distinct paths from A to B will form a cycle. Jan 9, 2013 at 19:54
• @AaronD: so, which one did you used in the end? Jan 15, 2013 at 9:30
• @arnaud: I'm not certain I've settled on an algorithm yet; I'll add an update to this question when I have. I eliminated Eppstein because it doesn't guarantee acyclic (aka 'simple') solutions. I'm currently working with Yen's algorithm, but I haven't yet gotten to detailed profiling or optimization, so I may have to replace it with another one. I'll update in the next week or two. Jan 15, 2013 at 17:06

To partially answer my own question:

Since posting this question, I discovered that we need to handle negative edge weights as well as positive (the limitation to acyclic / simple / loopless paths means that the best solution is defined, whereas without that limitation the shortest path through a graph with negative-cost cycles is undefined).

Yen's algorithm, and most of the others I examined, depend on a series of 1-best searches; most use Dijkstra for those intermediate searches. Dijkstra does not support negative edge weights, but we can substitute Bellman-Ford in its place (at least in Yen; presumably in Lawler or Eppstein as well). I've developed a modification of Bellman-Ford with a path-length limitation (in edges) and explicit cycle-checking during search (in place of the standard post-search cycle detection). The computational complexity is worse, but still tractable for my requirements. I'll edit this response and link to a tech report if I get permission to post it.

I would say this question can be easily googled and is also a duplicate:

That being said, I already used and implemented Eppstein and recommend it. I found it quite elegant. If I remember right, it may be optimal as well, and the following paper explains it very nicely:

http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf

• First, thanks for the recommendation of Eppstein. I'll look more there. I'd argue that this isn't an exact duplicate, nor is it easy to google; it's easy to find a k-best algorithm, but not so easy to choose sensibly between them. I expect I'd want a very different algorithm for a sparsely-connected graph of millions of vertices than I will for this problem. I would care a lot more about complexity in k if I wanted the 1000-best instead of 10-best. And, while constant factors aren't that important when publishing papers, they certainly are when shipping production code. Jan 9, 2013 at 23:01
• @AaronD: just for your information, I think the algorithm is very efficient whatever the case. Perhaps there are special cases where heuristic driven searches beat it, but for the general case, I think it does very well. The exact performance will probably depend more on how exactly you implement it, the efficiency of your datastructures and how tailored to your problem it is. Jan 10, 2013 at 10:41
• @arnaud Hi, is it possible for you to share your eppstein's implementation? I have a similar question posted here: math.stackexchange.com/questions/1661737/… May 3, 2016 at 16:31