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

Question

I know A* algorithm can find the shortest path. But the problem in my work is that I need to find all the shortest paths. More precisely, there may exist several shortest paths, but I need to choose the one shortest path in the precedence of clockwise.

If I can get all the shortest paths, I can get the one(clockwise precedence) I want.

Answer 1

To clarify what @penelope meant by: "... just keep going after you find the first optimal solution ..."

To get a set of equivalent cost optimal paths from A*:

Once A* has found a shortest path (cost=C*), you can get other paths of equivalent length by continuing to pop solutions off of the OPEN list until you encounter a solution costing more than C*. (there is a caveat, if your heuristic is not perfect, you may have to do some extra work.) Note that this will give you a set of optimal paths, but not necessarily the set of all optimal paths - that depends on how you've set up duplicate detection.

To get a clockwise path from A*:

As for preferring clockwise paths, consider using tie-breaking in your comparison method for sorting the OPEN list. If two candidates have the same f-cost, prefer the one that is most clockwise. (I think you can get a notion of clockwise-ness by looking at your candidates relative to the start/goal nodes.) If you tie-break in this way, clockwise solutions will be pushed to the front of the OPEN list and you will get the most clockwise solution from A*.

Answer 2

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.

Answer 3

Dijkstra's algorithms gives you all the shortest paths. A* was made as an improved Dijkstra, with additional constraints. The improvement was you didn't need to visit all the nodes. If you want to explore all the nodes (which is mandatory to make sure you have checked all the shortest paths), then there is no point using A*, just stick to the general-purpose ancestor