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.
5
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:
- 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
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 |