Ideal algorithm for finding all paths in a graph
You should use modified BFS algorithm (http://en.wikipedia.org/wiki/Breadth-first_search). On each vertex you should save list of neighbors, which are leading to this vertex(predecessors) instead of having just 1 neighbor leading to this vertex.
When you want to find all paths from this you just have to start on your end node and branch your path at every vertex, that have more than 1 predecessor and go with the way created by predecessors in each vertex until you get to start node with all branches you have.
EDIT: You can use DSF algorithm instead of BFS and modify it in a same way.
Related videos on Youtube
None None
Updated on June 13, 2022Comments
-
None None over 1 year
Let's take this graph for example:
Now let's say I'm starting at vertex 3 and want to find vertex 7. Depth first search (depending on the implementation) will look at the children first. Now, in our example, for the sake of the argument, I start at vertex 2, then go to vertex 4 and vertex 2, returns to vertex and goes to vertex 7, problem solved.
What I'd like: I'd like to get all the possible paths that would get me from x to y (e.g. 3 to 7: 3,1,4,7 - 3,5,7 - 3,4,7 - 3,5,6,9,7). That I don't get from Depth first search.
What is the algorithm you'd suggest?
Thank you!
-
jlahd about 10 yearsYou do got that from DFS, if you simply do not stop the search at the first acceptable solution. So instead of saying "problem solved", just write down the solution and continue.
-