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
Recommended Answers
Jump to PostThere'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 …
Jump to PostA nornal BFS will cover all the routes in a logical order until it has covered them all, won't it?
Jump to PostIf 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 …
All 9 Replies
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.