我需要一个算法，用于查找将使用递归迷宫最短路径。这是我的理解是使用递归算法通常DFS。

I need an algorithm for finding the shortest path in a maze that will use recursion. It is my understanding that algorithms that use recursion are usually DFS.

我一直在寻找所有在互联网上，大部分的结果都只是Dijkstra算法，这是不递归。是否有人可以提供一个伪code或点我朝着正确的方向？

I have been looking all over the internet and most results are just Dijkstra's algorithm, which is not recursive. Can someone please provide a pseudo code or point me to the right direction?

感谢你。

推荐答案

为什么你需要使用递归？最简单的算法寻找最短路径的 BFS 的，而不是DFS，它是不是递归。我知道没有又好又快一般情况下，最短路径算法，使用递归。

Why do you need to use recursion? The most simple algorithm for finding the shortest path is BFS, not DFS, and it is not recursive. I know of no good and fast general-case shortest path algorithm that uses recursion.

还要注意，如果你的图（迷宫）是的树的，即没有循环，然后从每个顶点对方只有一个办法，这将是最短的，所以DFS将适用于这种情况。

But also note that if your graph (maze) is a tree, i.e. has no cycles, then from each vertex to each other there is only one way, and it will be shortest, so DFS will be applicable in this case.