CODEWITHSUNDEEP
javaalgorithmdepth-first-search
Alice
Alice

Reputation: 1400

A recursive DFS template to find the shortest path

I am learning DFS through dfs-template I - LeetCode

It introduced a recursion template 

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

A question raised in the end

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.

How to find the shortest path?

I assumed that a step parameter should be added to remember depth of each turn to traverse, after exhausted all all the possible paths, compare the depths and return the minimal.

Where is the parameter step placed?

Upvotes: 2

Views: 1427

Answers (1)

jennifer lawrence
jennifer lawrence

Reputation: 535

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

the array distances will store shortest path for every node

Upvotes: 1

Related Questions