Finding all unique paths from a source to a sink in a specially-formed DAG
If you are interested enumerating all the unique paths, then a recursion would be suitable since it is a dag. Observe that suppose v is a non source vertex and has incoming arcs from X1,...,Xn then every path from the source through v needs to pass through X1,...,Xn. . So if you enumerated all the paths from the source to each of these vertices you simply need to append v to them to compute all the paths through v originating from the source. This computation can be done very efficiently via dynamic programming. The reason DP will work is precisely because none of the paths from source to X1,...,Xn would have contained v since it is a dag.You should be able to work out the time complexity for the algorithm i described easily since it has a standard dp structure.