昨晚到今天，我一直在网上广泛搜索，似乎找不到讨论如何通过专门使用回溯算法来解决最短路径问题的资源。我尝试用这个算法解决它，但对我来说没有意义。如果是n皇后问题，就不会这么复杂了。
那么任何人都可以提供一些可以指向我一些资源的互联网链接吗？我非常感激。
*更新：只是好奇，回溯算法真的能解决最短路径问题吗？
问问题
3787 次
2 回答
1
您指定使用回溯算法是有线的，实际上 dijkstra SPFA 或 bellman-ford 算法将完美地解决您的问题。如果你必须使用回溯，恐怕你只能达到一个糟糕的时间复杂度——试试你的下一个路段，当你选择的路段的总长度超过“当前最短路径”时，开始回溯。
于 2012-01-14T06:50:38.627 回答
-1
回溯可以解决它。但它很慢......我认为你需要 Dijkstra O(n^2)，Dijkstra with heap O(nlogn)，Bellman-ford O(ne) 或 SPFA O(ke)(k≈2 ). 至于我，我更喜欢 SPFA...
于 2016-01-25T11:29:07.977 回答