Is DFS (Depth-first search) algorithm applied on an adjacency matrix the ideal solution to list all root-to-leaf paths of a graph?

Question

I am creating a function in Ruby to list all the possible paths that a business process may be executed. Look at the diagram below that represents a sample process:

I want the output to be like:

[
  [[Task 1],[Task 2], [Task 4], [Task 6]],
  [[Task 1],[Task 3],[Task 5],[Task 6]]
]

So, I created a method to represent it as an adjacency matrix. It works just fine.

Now I want to work on an algorithm to extract all those paths. I was gonna implement the DFS, but I'm not so sure anymore if this is the right way to approach it since I'm not doing an actual search - I am only listing the paths.

DFS will work just fine, why are you not sure whether it's "the right way"? — Bernhard Barker, Aug 04 '17 at 20:21
@Dukeling because, in a first moment, I thought DFS was only for searching for a specific vertex. I have little knowledge in algorithms and graph theory too. — Leandro, Aug 05 '17 at 17:01
@marvel308 yes, and as soon as one user pointed that out I updated my question — Leandro, Aug 05 '17 at 17:02

score 0 · Answer 1 · answered Aug 04 '17 at 19:38

0

The problem is np-hard because the number of possible paths between two nodes is exponential to the number of nodes since the example given is a DAG instead of a tree. so no way around having a worst-case exponential runtime. DFS/BFS would be the best way to go please refer to
Finding all paths between two nodes on a DAG
Enumerating all paths in a directed acyclic graph

answered Aug 04 '17 at 19:38

marvel308

10,288
1
21
32

wow, thanks a lot. I didn't even know what a DAG was. I'm gonna read thoroughly those links and I will give feedback later – Leandro Aug 04 '17 at 19:52

Is DFS (Depth-first search) algorithm applied on an adjacency matrix the ideal solution to list all root-to-leaf paths of a graph?

1 Answers1