1

How could A* algorithm be efficiently modified to provide e.g. 2nd or 8th shortest path, not first?

c0der
  • 18,467
  • 6
  • 33
  • 65
Gintas_
  • 4,940
  • 12
  • 44
  • 87
  • Do you have any ideas about how you might do that? This is a pretty broad question (though I personally don't think it falls under Too Broad), so it may be good if you provide a couple of ideas on how you are thinking of approaching the problem, so that people can discuss those or present better options. – Kevin Mar 14 '16 at 16:53
  • Nope and I don't find any information about it on Google. I only know I could add random cost, but that would be a random path, not n-th shortest path – Gintas_ Mar 14 '16 at 16:56

2 Answers2

1

If at all possible, I suggest that you try and make your program look like a shortest path problem to which Dijkstra applies, and then use one of the answers you have already been pointed at to find the kth shortest path in this situation, such as Eppstein's algorithm and Yen's algorithm for k shortest paths.

But there is another approach. There is a general technique for finding the Kth best answer to combinatorial problems by adding extra constraints which allow you to split the solution tree. It is known as Lawler-Murty and is described for example in section 2 of http://www.vldb.org/pvldb/vol4/p1028-golenberg.pdf

Community
  • 1
  • 1
mcdowella
  • 19,301
  • 2
  • 19
  • 25
0

You should check out the algorithm K*. It was published in a paper titled: "K*: A heuristic search algorithm for finding the k shortest paths". The paper was published in the research journal Artificial Intelligence in 2011 (one of the most prestigious in the field), so, as far as I know it is kind of state-of-the-art for what you are looking for.

If you used the algorithm with a consistent heuristic has an asymptotic worst-case complexity of O(m + n log(n) + k) in runtime and space (where n is the number of vertices and m the number of edges in the graph).

FrankS101
  • 2,112
  • 6
  • 26
  • 40