How can I use the A star algorithm to find the fir

Question

How can I use the A star algorithm to find the first 100 shortest paths?

Answer 1

Besides of this problem being NP-hard, it is impossible to do this with A* or dijkstra without major modifications. Here are some major reasons:

First of all, the algorithm keeps at every step only the best path so far. Consider the following Graph:

  A
 / \
S   C-E
 \ /
  B

Assume distances d(S,A)=1, d(S,B)=2, d(A,C)=d(B,C)=d(C,E)=10.

When visiting C you will pick the path via A, but you will nowhere store the path via B. So you'd have to keep this information.

But, secondly, you don't even consider every path possible, assume the following graph:

S------A--E
 \    /
  B--C

Assume distances d(S,A)=1, d(S,B)=2, d(B,C)=1, d(A,E)=3. Your visiting order will be {S,A,B,C,E}. So when visiting A you can't even save the detour via B and C because you don't know of it. You'd have to add something like a "potential path via C" for every unvisited neighbor.

Thirdly, you'd have to incorporate loops and cul-de-sacs's , because yes, it is perfectly possible that a path with a loop in it ends up being one of your 100 shortest paths. You'd of course might want to constraint this away, but it is a generic possibility. Consider for example graphs like this:

S-A--D--E
  |  |
  B--C

It's clear you can easily start looping here, unless you disallow 'going back' (e.g. forbid D->A if A->D already in path). Actually this is even a problem without an obvious graphical loop, because in the generic case you can always ping-pong between two neighbors (path A-B-A-B-A-...).

And now I'm probably even forgetting some issues.

Note that most of these things make it also very hard to develop a generic algorithm, certainly the last part because with loops it is hard to constrain your number of possible paths ('endless loop').

Answer 2

Use a* search, when the destination is k-th time pushing into the queue. It would be the k-th shortest path.

Answer 3

This is not an NP hard algorithm, and the below link is the Yen's algorithm for computing K-shortest paths in a graph in polynomial time. Yen's algorithm link

Answer 4

The problem of finding k'th shortest path is NP-Hard, so any modification to A-Star that will do what you are after - will be exponential in the size of the input.

Proof:
(Note: I will show on simple paths)
Assume you had a polynomial algorithm that runs in polynomial time and returns the length of kthe shortest path let the algorithm be A(G,k)

The maximal number of paths is n!, and by applying binary search on the range [1,n!] to find a shortest path of length n, you need O(log(n!)) = O(nlogn) invokations of A.
If you have found there is a path of length n - it is a hamiltonian path.
By repeating the process for each source and target in the graph (O(n^2) of those), you can solve the Hamiltonian Path Problem polynomially, assuming such A exists.
QED

From this we can conclude, that unless P=NP (and it is very unlikely according to most CS researchers), the problem cannot be solved polynomially.

An alternative is using a variation of Uniform Cost Search without maintaining visited/closed set. You might be able to modify A* as well, by disabling the closed nodes, and yielding/generating solutions once encountered instead of returning them and finishing, but I cannot think of a way to prove it for A* at the moment.