 user3194972 -4 years ago 97
Java Question

# Finding a single path in a graph using dfs

I am currently trying to find a single path in a graph leading from source to sink. I am trying to implement a method using dfs to achieve this. However, i can't seem to figure out how to make the method to stop the recursion. For example, i have this graph (in matrix form)

0 1 1 0

0 0 0 1

0 0 0 1

0 0 0 0

So i have an edge from node 0 (the source) to node 1 and 2 respectively, and then an edge from 1 and 2 leading to 3 (the sink). The path i would want to have would be 0>1>3, instead i'm getting 0>1>3>2>3. How can i make the recursion stop as soon as a path to the sink is found?

Here is the code for the method:

``````public void dfsPath(int i) {

boolean[] visited = new boolean[this.edgeCapacities.length];
visited[i] = true;
this.path.add(i); //Integer ArrayList containing the nodes in the path

//loop through all of the nodes in the matrix to find adjacency
for (int j = 0; j < this.edgeCapacities.length; j++) {
//check if edge exists and node has not been visited
if (this.edgeCapacities[i][j] != 0 && !visited[j]) {
//here is the problem, i want the recursion to stop once the sink is found
//it does not work however.
if(j == this.sink) {
visited[j] = true;
this.path.add(j);
return;
} else {
//recursion
dfsPath(j);
}
}
}
``````

Any help would be greatly appreciated. Thanks in advance. tobias_k
Answer Source

There seem to be several problems with your DFS algorithm:

• by creating a new `visited` list in each recursive call, it always contains only the current node
• you are only adding nodes to `this.path`, but never removing nodes that did not lead to the goal
• you never check whether one of your recursive calls reached the goal, thus adding more nodes to a perfectly good path

To fix this, you should remove the current node from `this.path` at the end of the method, i.e. in case no path has been found. Also, you can just drop the `visited` array and just check whether the next node is already in the path. That's not quite as fast, but should suffice for your case and make the code less complex. Also, the method should return `true` or `false` depending on whether it found a path.

Try this (not tested, but should work).

``````public boolean dfsPath(int i) {
this.path.add(i); // add current node to path
if (i == this.sink) {
return true; // if current node is sink, return true
// this.path contains nodes from source to sink
}
for (int j = 0; j < this.edgeCapacities.length; j++) {
if (this.edgeCapacities[i][j] != 0 && ! this.path.contains(j)) {
if (dfsPath(j)) {
return true; // found a path -> search no further
}
}
}
this.path.remove(this.path.size() - 1); // pop last node
return false; // no path found
}
``````

Note that I also moved the `sink`-check out of the loop. This is purely a matter of taste, but it makes the code a bit simpler, as you don't have to add the `sink` node separately to the path.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download
Latest added