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

Question

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.

• KChaloux: +1, because I'm interested in the suggestions people have, and this seems like the exact type of question this site was made for.
• user470365: 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.
• AaronD: 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.
• dagnelies: @AaronD: so, which one did you used in the end?
• AaronD: @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.

Answer 1

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.

Answer 2

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

• https://stackoverflow.com/questions/12773525/k-shortest-alternative-path-algorithm-java-implementations
• https://stackoverflow.com/questions/7208720/finding-kth-shortest-paths

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

• AaronD: 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.
• dagnelies: @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.
• Mary: @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/…

Answer 3

Please refer the table below to make the best choice.

Algorithm	Time Complexity (Big O)	Space Complexity (Big O)	Direct or undirect graph?	Handle cyclic graph?	Handle negative edge weight?	When to use?
Dijkstra's Algorithm	(E+V)LogV	V	Both	No	No	Get shortest paths from single source to all vertices
Bellman-Ford Algorithm	VE	V	Both	Doesn't work for negative weight cycle	yes	Get shortest paths from single source to all vertices
Topological sort Algorithm	V+E	V	Direct	No	Yes	Get shortest paths from single source to all vertices
Floyd-Warshall algorithm	V^3	V^2	Both	Doesn't work for negative weight cycle	Yes	Get shortest paths from all vertices to all vertices