how to find the best three routes using A* algorithm

Question

In A* usually the result that you get is only one path. Is it possible though for a given origin and destination to have 3 recommended path according to A*? So the second returned is the second best path, and the third is the third best path..

I was thinking of maybe modifying the heuristic somehow to reflect this second and third best path.. What do you guys think?

UPDATE: My implementation is in PHP and I am using a closed set. So if there's a way to do this, let me know.

Answer 1

This can be done quite easily if your language has support for backtracking/generators/iterators/coroutines.

# Python code
def astar(start):
    q = [start]    # priority queue
    while len(q) > 0:
        node = heappop(q)
        if isGoal(node):
            yield node
        for x in successors(node):
            heappush(q, x)

The yield keyword is similar to return, except that the function may be re-entered after a yield to get the next solution. To get the best three:

solutions = []
i = 0
for sol in astar(start):
    solutions.append(sol)
    if i == 3:
        break
    i += 1

However, this will not work if you use a closed set (i.e., Russell & Norvig's graph search algorithm), since then part of the non-optimal solutions may be "cut off" when searching for the optimal one.