# Finding all paths from s to t in linear time

I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't understand

The basic idea is :

1. DFS-Visit(s)
2. Change current status to "currently visiting"
3. If neighbor is t -> print the path (from the stack trace or any way)
4. If not: DFS-Visit on neighbors
5. When done visiting neighbors: change status to "not-visited yet"

It seems like it's run-time is exponential, however - could I use the memorization technique like in dynamic programming to turn this into linear time ? since a lot of calculations are repeating

The example given in the algorithm is a DAG, but I couldn't find an regular graph that makes this algorithm fail.

It seems highly unlikely that this algorithm is possible in linear time on a regular graph... Wouldn't that help me to calculate shortest path from s to t in linear time ?

• in a fully connected graph the number of paths from $s$ to $t$ will be $O(n!)$, kinda hard to get a linear time algorithm to print them all – ratchet freak Jul 7 '17 at 9:57
• @ratchetfreak Only if you consider simple paths only. Otherwise it's worse. (Also, $\Theta$!) – Raphael Jul 7 '17 at 10:33
• Closely related question. Or any of these. Duplicate? – Raphael Jul 7 '17 at 10:34
• Finds all paths from $s$ to $t$ in $O(n)$? This means we could easily find the longest path in $O(n^3)$ simply by checking all pairs of nodes and all paths between them. So your guess about it not running in linear time on a regular graph is probably accurate. Although if you just have a DAG then it might be more reasonable because the longest path can be found in linear time. So I would recommend sticking to DAGs. – ryan Jul 7 '17 at 15:30

The algorithm you describe cannot possibly be linear time for a DAG or general graph. Consider the following DAG on $$n$$ vertices $$V = \{v_1, v_2, \ldots v_n\}$$. Take a particular node $$v_i$$, for all $$j > i$$ add an edge $$(v_i, v_j)$$. This will create $$\Theta(n^2)$$ edges in this DAG. Note that a path from $$v_1$$ to $$v_n$$ can use any subset of nodes $$\{v_2, v_3, \ldots v_{n-1}\}$$. That is to say there are $$2^{n-2}$$ possible paths from $$v_1$$ to $$v_n$$. Clearly to print all these would take exponential time.
What you can do in linear time, is determine the subgraph that would contain all possible paths from $$s$$ to $$t$$. With a source $$s$$ in mind, we first check if it can reach $$t$$ (via DFS), if not then return an empty subgraph. Otherwise we check if $$s$$'s children $$\{v_1, v_2, \ldots\}$$ can reach $$t$$, this can be done recursively top-down or bottom-up if we start at $$t$$ and work backwards. Let's say $$A$$ is the set of nodes who are a descendant of $$s$$ and an ancestor of $$t$$. $$A$$ will also include $$s$$ and $$t$$ for obvious reasons. The subgraph we are interested will contain exactly the vertices in $$A$$. With this we can iterate through edges an include them as necessary, or we could even pick up edges long the way as we are determining which nodes are in $$A$$. This procedure overall will take $$O(n + m)$$. Of course, this is only interesting in a DAG unless $$t$$ or $$s$$ is an articulation point.