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.

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

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