CODEWITHSUNDEEP
algorithmgraphroutesshortest-path
fuzzomorphism
fuzzomorphism

Reputation: 77

Find several shortest paths with A* algorithm

I am making a routing application that uses A* algorithm for finding route. I want to offer not just one route, but also a few alternative routes. For example routes that are just a little bit longer than the optimal one.

Since A* (and many others) find only one route, how can I search for these alternative ones? Should I use some other algorithm?

Upvotes: 1

Views: 949

Answers (2)

Luna
Luna

Reputation: 392

You may want to look into research on the K shortest paths problem, which is the problem of finding the k shortest paths between two nodes. The algorithm described on the Wikipedia page is a generalisation of Dijkstra's algorithm.

To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path. The K Shortest path routing algorithm is a generalization of the shortest path problem. The algorithm not only finds the shortest path, but also K other paths in order of increasing cost. K is the number of shortest paths to find. The problem can be restricted to have the K shortest path without loops (loopless K shortest path) or with loop.

Some key papers and concepts:

Upvotes: 3

amit
amit

Reputation: 178521

One possible solution is to run A*-epsilon with increasing value of epsilon.

With each iteration, as epsilon grows, the path found is expected to be longer - and the time for finding it to be shorter.

Upvotes: 1

Related Questions