CODEWITHSUNDEEP
javaalgorithmgraph-theory
isaacsultan
isaacsultan

Reputation: 3974

Iterative DFS to find path from source to destination

I would appreciate help debugging my implementation of DFS to find a path. My implementation generally works well but in a certain edge case will add an extra node to the result which is visited by the algorithm but should not included within the solution as a path from it to the next node in the result list does not exist. The issue is likely to be caused by where Result.add(nextNode) is positioned, but I have not been able to fix this bug.

An example of the problem is attached below (weights arbitrary), whereby the algorithm returns [0 2 4 1 3 5] as a result even though no edge from 4 to 1 exists.

Example

Can anybody suggest how to modify my code so that a node like 4 is not added to the result please? 

 public static ArrayList<Integer> pathDFS(Integer source, Integer destination, WeightedGraph graph) {
            ArrayList<Integer> Result = new ArrayList<Integer>();
            ArrayList<Integer> Visited = new ArrayList<Integer>();
            Stack<Integer> s = new Stack<>();
            s.push(source);
            Visited.add(source);
            while (!s.isEmpty()) {
                Integer v = s.pop();
                    for (int nextNode : getAdjacentNodes(v, graph)) {
                        if (!Visited.contains(nextNode)) {
                            s.push(nextNode);
                            Visited.add(nextNode);
                            **Result.add(nextNode);**
                            if (nextNode == destination)
                                return Result;
                    }
                }
            }
            return Result;
        }

Upvotes: 1

Views: 3583

Answers (1)

kraskevich
kraskevich

Reputation: 18556

Adding the node to the result list every time you add it to visited list is clearly wrong (the set of visited nodes is not necessarily contains just the path. It can have a bunch of other nodes, not just one).

To fix it, you can create a parent list to store the parent of each node (and populate it when discover a new node). This way, you'd just need to go from the target node by the parent links to the source to reconstruct the path.

Upvotes: 1

Related Questions