Ideal algorithm for finding all paths in a graph

10,598

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.

Share:
10,598

Related videos on Youtube

None None
Author by

None None

Updated on June 13, 2022

Comments

  • None None
    None None over 1 year

    Let's take this graph for example:

    graph

    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
      jlahd about 10 years
      You 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.

Related