backtracking algorithm to solve shortest path?
https://stackoverflow.com/questions/8860572
-
28-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
I have been extensively searching all over the net last night until today and I can't seem to find a resources discussing how to solve the shortest path problem by specifically using the backtracking algorithm. I tried solving it with this algo but I doesn't make sense to me. If it's the n-queens problem, it wouldn't be this complicated.
So can anyone give some internet links that would point me to some resources? I appreciate it very much.
*UPDATE: Just curious, can the backtracking algorithm really solve the shortest path problem?
解决方案
It is wired you specified to use backtracking algoritm, in fact dijkstra SPFA or bellman-ford algorithm will be perfect to solve your problem. If you HAVE TO use backtracking, I am afraid that you could only reach a bad time complexity----just try your next road segment, and when the sum length of your chosen segments exceeded "current shortest path", start backtracking.
其他提示
Backtracking can solve it.But it is very slow...I think you need Dijkstra O(n^2), Dijkstra with heap O(nlogn), Bellman-ford O(ne) or SPFA O(ke)(k≈2).As for me, I prefer SPFA...
