backtracking algorithm to solve shortest path?

Question

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?

Answer 1

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.

Answer 2

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...