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;
}

距离数组将存储每个节点的最短路径