[Java] Find all paths from source to dest in a directed acyclic graph

Given a DAG, find all paths from source to target.

Since it is a DAG, there are no cycles, therefore we can't go back to an already visited vertex during a visit.

We can therefore add the source to a stack, then use recursion to find all paths from source to target.

In the recursive function, we look at the current node (top of stack) and for each one of its edges, we add the destination to the stack and call recursion on that destination.

When the top of stack is the target, we scan the scan and track all elements as a solution, they will be in inverted order from last vertex to first. However, a foreach loop on a Stack (in Java) gives element in order from bottom to top, so there is no need to invert them in our result.

When we get back from a recursive call, we remove ourselves from the stack as we have fully explored our subgraph.

This code works in O(V) space as that's how deep the recursion could go, and our stack also matches the recursion in size.

For time complexity, I assumed we would get a O((V+E)^2) upper bound as without cycles we cannot go back to previously visited vertices but some paths might overlap and we would walk down the same edge multiple times.

This might not be the case if we look for ALL paths from ALL vertices, however we only consider ONE start vertex in this case.

I think it made sense as a similar problem which is topological sorting is linear and in this case we're looking at all paths between the two farthest nodes.

Turns out it's exponential in reality:  If all vertices are connected (without cycles) for each new node excluding start and end, we have a choice of either including it in a path or not, which would give a O(2^V) upper bound.

You can check my implementation of findAllPathsFromSourceToDestInDAG on my Gist along with some tests in FindAllPathsFromSourceToDestInDAGJTests.