Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
+1, because I'm interested in the suggestions people have, and this seems like the exact type of question this site was made for. –  KChaloux Jan 9 '13 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. –  user470365 Jan 9 '13 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. –  AaronD Jan 9 '13 at 19:54
    
@AaronD: so, which one did you used in the end? –  arnaud Jan 15 '13 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. –  AaronD Jan 15 '13 at 17:06
add comment

migrated from stackoverflow.com Jan 9 '13 at 14:40

This question came from our site for professional and enthusiast programmers.

2 Answers

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

share|improve this answer
    
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. –  AaronD Jan 9 '13 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. –  arnaud Jan 10 '13 at 10:41
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.