Some time ago, I wrote some code, which uses DFS to find whether there is a path from a source vertex to a destination vertex. However, I am thinking now what if there is more than 1 possible way? What comes to my mind is save paths in an ArrayList as Arralist of integer and then for every path source-destionation check whether it was found already or not? Just like visitting the nodes, mark them as visited. Actually when I think about it, only visitted nodes should be enough won't even need to check whether paths are identical or noth since it won't repeat the visitted nodes path again, but it has to be done in a loop now, what should the stopping condition be? What I do now is using DFS, as soon as the path is found it returns true and the search stops (my dfs is decleared as boolean, just wanted to check whether path exists or not). I guess it has to be similiar to Dijkstra's algorithm for the shortest path if there is cost added between the edges but in this case to display all paths not to return the shortest one? Any suggestions on how to the logic behind not stopping to execute until no unchecked nodes exist? How about having an arraylist with all vertexes, and the arraylist which gets all visited, if i compare the size of those, it should loop until it has been to every vertex right? as in while(!(allVertex.size() == visitedVertex.size())), but in this case how would I print out only those paths that reach the destination and not every visited vertex? Sorry for the essay :D
Oh, and I think Dijkstra's algorithm is using BFS, so it doesn't really show all possible ways to distination just the shortest one :D
There's two parts to this:
Easy: When doing the DFS and you find a path, instead of stopping just add the path to an ArrayList and keep going. The DFS algorithm should ensure every path is visited exactly once.
More interesting: exactly how do you define and instantiate a single Path so you can add it to the List? Maybe a Path is just a List of node numbers, that would certainly be a good place to start.
WHat kind of stopping condition would I have? Even if it finds all posible moves it will just keep trying unless there is something, and can't really think of anything other than compare the size of all nodes and those to visited nodes? That should ensure that every three path is checked ye?
A nornal BFS will cover all the routes in a logical order until it has covered them all, won't it?
If you are looking for all paths possible, DFS or BFS can do. DFS and BFS are not about the shortest path but they are simply a way to go through the path in different way. It is incorrect to say that DFS is to find the shortest path.
The only difference between finding a path and all paths is how to set your termainated condition. Either DFS or BFS, you simply keep going through until you have cover every path possible. If you find a solution path, store the solution somewhere and keep going on the search until you hit all possible visits...
I never said bfs/dfs was for finding shortest path? Said that when I mentioned Dijktra's algorithm :D thanks James i ll write the few missing lines then and see if it works the way i think
It is incorrect to say that DFS is to find the shortest path.
DFS can be used to find the shortest path, or finding (a) path(s) of (a) particular condition(s) for that matter.
WHat kind of stopping condition would I have?
Does the graph have cycles? If it does, then you need to keep track of which ones you have visited (I would keep track of these in a hash set, for the sake of concurrency), and backtrack if you reach a vertex you have already visited. Otherwise your right, your program would not terminate and have incorrect paths all over the place until you run out of memory, or stack overflow. If it doesn't have cycles, then just looping though all of the adjectent vertexs will terminate itself (and visit each path exactly once).
Good point about cycles Hiroshe. When talking about DFS searched being exhaustive and terminating I should have mentioned the need to reject solutions that re-visit a node that has already been visited (or some equivalent loop-prevention mechanism).
Okay .. I've been really busy irl lately, I am back on tract now, kept the thread opened until I get the idea to work. Here is what I did after fixing some of my code is to save the path in an array of integers and then print it out
public class multiplePaths {
private static HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
private static ArrayList<Integer> visitedVertices = new ArrayList<Integer>();
private static ArrayList<Integer> paths = new ArrayList<Integer>();
public static void main(String[] args){
ArrayList<Integer> al = new ArrayList<Integer>();
al.add(3);
al.add(4);
graph.put(1, al);
graph.put(2, new ArrayList<Integer>(Arrays.asList(4,5)));
graph.put(3, new ArrayList<Integer>(Arrays.asList(1)));
graph.put(4, new ArrayList<Integer>(Arrays.asList(1,2,7)));
graph.put(5, new ArrayList<Integer>(Arrays.asList(2,6)));
graph.put(6, new ArrayList<Integer>(Arrays.asList(5)));
graph.put(7, new ArrayList<Integer>(Arrays.asList(7,4)));
graph.put(8, new ArrayList<Integer>(Arrays.asList(9)));
graph.put(9, new ArrayList<Integer>(Arrays.asList(8)));
checkAndClear(1,6);
//System.out.println(checkAndClear(1,2));
//System.out.println(checkAndClear(1,7));
//System.out.println(checkAndClear(7,7));
}
private static boolean isConnected(int vertex1, int vertex2) {
visitedVertices.add(vertex1);
if (graph.get(vertex1).contains(vertex2)) {
paths.add(vertex2);
System.out.println(paths);
return true;
}
else if(vertex1 == vertex2){
return true;
}
ArrayList<Integer> a = graph.get(vertex1);
//System.out.println(a);
for (int i = 0; i < a.size(); i++) {
int vis = a.get(i);
if(!visitedVertices.contains(vis)) {
paths.add(vis);
//System.out.println(vis);
if (isConnected(vis, vertex2)) return true;
}
}
return false;
}
private static boolean checkAndClear(int vertex1, int vertex2){
boolean result = isConnected(vertex1,vertex2);
visitedVertices.clear();
return result;
}
}
Any suggestions on where to go from now on? the second method was meant just to clear the visitedVertices in case few tests were run back to back
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.