How can I use the A star algorithm to find the first 100 shortest paths?
Asked
Active
Viewed 3,247 times
3
-
What do you hope to use those paths for? An n-th shortest path will usually be the shortest path with a detour at some point and will not be useful for any practical purpose. There may be some reasonable alternate path, but than the difficult problem is how do you tell whether path looks "reasonable" to a human. – Jan Hudec Jan 02 '13 at 10:14
-
@Jan Hudec: In my programme I'm going to implement flight search system. Cost of the edges are the flight duration.I'm going to find the priced flight solutions.But the quickest path may not be a cheap path.So I'm going to first find the 100 quickest flights and then going to price the paths accordingly. – user1815763 Jan 02 '13 at 10:40
-
100 quickest flights will give you heaps of garbage and might not actually give you any cheap path, because there is absolutely no way to know how far the cheap path is. Instead you either want to find all minimal paths based on partial ordering (created by combining various criteria), or run the algorithm multiple times with different target function. Or apply heuristic limits for depth and distance and do exhaustive search; I suspect it would be viable for flights, though not for, say, bus connections. – Jan Hudec Jan 02 '13 at 15:21
-
Anyway, that's a completely different question, so more detailed discussion after you formulate new question - either "how to search in time-table with multiple criteria (cheaper, shorter, faster etc.) and find all paths that are minimal in any of them" or "how to search in flight time-table when many alternative results are desired". Or both, if you are interested. – Jan Hudec Jan 02 '13 at 15:24
-
If you're implementing this for flights search system you might want to have a look into alternative routes: http://algo2.iti.kit.edu/2073.php, http://algo2.iti.kit.edu/english/1805.php, etc – Karussell Jan 05 '13 at 17:32
4 Answers
8
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.
amit
- 175,853
- 27
- 231
- 333
-
Could you explain me how to find the first 100 shortest paths using A*? I implemented A* to find the shortest path. A used an admissible heuristic. Now I want to find the first 100 shortest paths. – user1815763 Jan 02 '13 at 10:14
-
Could you explain me how to find the first 100 shortest paths using A*? I implemented A* to find the shortest path. Also used an admissible heuristic.Disabling the closed node list will allow us to reuse the previously visited nodes. But now I want to find the first 100 shortest paths.Please explain how to do it. – user1815763 Jan 02 '13 at 10:24
-
@user1815763, You will need to "push" into the priority queue the entire paths (source->v1->v2->..->vn) (and its score of course) and at each step insert all next available paths, ignoring which vertex you have already visited or not (visit all of them). Whenever you pop from the queue some element that is the destination - you found a path. I believe (though cannot prove at this point) that the kth time you pop a destination from the queue is representing the kth shortest path. Note that this solution is exponential, because you don't limit yourself and can revisit nodes a lot of times. – amit Jan 02 '13 at 12:51
-
@KillianDS: No exactly, by disabling the closed nodes set, and revisitting closed nodes, you make the algorithm exponential - and it might result in solving the problem without proving P=NP (though I cannot prove at the moment that it will do so, but my gut says it will). – amit Jan 02 '13 at 12:51
0
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').
KillianDS
- 16,936
- 4
- 61
- 70
0
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
ghedas
- 325
- 2
- 13
-
Yen’s algorithm actually runs in [pseudopolynomial time](https://stackoverflow.com/q/19647658) because the runtime depends on the numeric value of k. Though for any fixed k - here, k = 100 - it will indeed run in polynomial time. – templatetypedef Jun 29 '20 at 21:32
-1
Use a* search, when the destination is k-th time pushing into the queue. It would be the k-th shortest path.
LazyChild
- 84
- 4
-
-
2
-
@Mehrdad When it is the first time destination pushing into queue, the value should be shortest path. Is that right? – LazyChild Dec 30 '12 at 07:05
-
@amit The correctness of a* depends on the heuristic h function. function h must be an [admissible heuristic](http://en.wikipedia.org/wiki/Admissible_heuristic). – LazyChild Dec 30 '12 at 07:11
-
@LazyChild: For shortest path - indeed. Assume you have the heuristic `h(v) = 0` (which is always admissible, and basically means your problem is uninformed. Could you prove the algorithm works for kth shortest path? (I doubt it, since I just showed the problem for general case `k` is NP-Hard, there must be other modifications such as disabling the `closed` set) – amit Dec 30 '12 at 07:15
-
@amit Yes. I should be more specific. We should use the distance `d` from the destination as the function `h`. And yes disabling the `closed` set is necessary. So one node could occur many times in the queue. – LazyChild Dec 30 '12 at 07:26
-
@ LazyChild could you please explain how to find the first k shortest paths(not k th) using A*? – user1815763 Jan 02 '13 at 09:31
-
This is incorrect. The dijkstra (and by extension A*) algorithms are destructive, for any node you only consider the best path so far. You'd actually have to consider any possible paths, even paths via nodes that have not been visited yet, because any small detour could lead to the second best path. – KillianDS Jan 02 '13 at 10:31
-
Consider for example a Graph with nodes `{S,A,B,C,E}`, connectivities `S-A, S-B, A-E, B-C, C-A` and all distances equal to `1`. You will never consider the path `S-B-C-A-E`. Why? Your visit order will be something like `S,A,B,C,E`. `A` and `B` might swap, so might `C` and `E`, because of equidistance, but it does not matter. You can see that when visiting `A` you don't even know of the detour coming via `C`, because `C` is unvisited. – KillianDS Jan 02 '13 at 10:34