java是一个递归DFS模板，用于查找最短路径

Question

我正在通过dfs-template I - LeetCode学习DFS

它引入了一个递归模板

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

最后提出了一个问题

In the template above, we stop when we find the first path.

What if you want to find the shortest path?

Hint: Add one more parameter to indicate the shortest path you have already found.

如何找到最短路径

我假设应该添加一个step参数来记住要遍历的每个回合的depth，在用尽所有可能的路径后，比较深度并返回最小值

参数step放在哪里

Answer 1

distances = new int[numberOfNodes];
boolean DFS(Node cur, Node target, Set<Node> visited, level) {
    for (next : each neighbor of cur) {
        if (next is not in visited and level + 1 < distances[next]) {
            distances[neighbor] = level + 1
            add next to visted;
            DFS(next, target, visited, level + 1)
        }
    }
    return false;
}

阵列距离将存储每个节点的最短路径