CODEWITHSUNDEEP
algorithmpathpath-findinga-star
Gintas_
Gintas_

Reputation: 5030

How could A* algorithm be efficiently modified to provide n-th shortest path?

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

Upvotes: 1

Views: 350

Answers (2)

FrankS101
FrankS101

Reputation: 2135

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).

Upvotes: 0

mcdowella
mcdowella

Reputation: 19601

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

Upvotes: 1

Related Questions