How to find all the shortest paths by using A* algorithm?

a-star, algorithm, shortest-path

Solution

The thing with the A* algorithm is that it is complete and optimal. That means that it will find a path to the solution if a path exists but also, that it is guaranteed to find the shortest path first.

That is because the heuristic function A* uses must be an admissible heuristic; that is, it must not overestimate the distance to the goal.

This in turn ensures that as soon as you find a path to the solution, you know that there are no paths shorter than that one in the rest of the search space.

Let's say that the distance to your first solution was d(problem). Now, my last statement actually means, if you just keep going after you find the first solution d(problem), and find another solution, d2(problem) there are two possibilities:

- d2(problem) = d(problem) : you want to keep that one since you want all the optimal paths. Also, all new paths can be equal to or larger than d2 = d

- d2(problem) > d(problem) : now, the same thing I wrote above is valid: there are no paths shorter than d2 anymore. And, d2 is already longer than the solutions you are looking for. So, you can discard d2 and finish your search

- note that there is no third option, d2(problem) can never be shorter than the optimal d(problem) you already found because that is one of the basic properties of the algorithm.

So, to summarize: you just keep going after you find the first optimal solutions, and you accept all the solutions that are of the same distance. First path that has a worse (longer) distance, you discard and stop your search.

I just saw the "clockwise" part of the question. You can probably avoid searching for all the optimal solutions by somehow inserting the clockwise-ness in to your heuristic or your cost function. E.g. a trick I've been using sometimes is: you have your cost as an integer number, going from 0 to inf. And then, you add the clockwise-ness component, that can have real values from the interval [0, 1) . This way, wherever it was true `a > b` before, it will stay so, but the relation `a == b` might be changed if the clockwise-ness component is different.

A different way you can compare, if you do not explicitly want to work with a numeric value, is to have the cost be a pair of values. If the first component of the pair is different in two path costs, you just compare those. If the first components are the same, only then you compare the second values in the pairs.

That said, off the top of my head, I am not sure if I would advise you to modify your cost or your heuristic function (or both). Also, I'm not sure if this precise trick will work in your problem, but I believe that you should be able to stir the algorithm towards the most clockwise solution just by modifying one of these functions if you just play a little.

Problem

Original source