1
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – ratchet freak Jul 7 '17 at 9:57
  • 1
    $\begingroup$ @ratchetfreak Only if you consider simple paths only. Otherwise it's worse. (Also, $\Theta$!) $\endgroup$ – Raphael Jul 7 '17 at 10:33
  • $\begingroup$ Closely related question. Or any of these. Duplicate? $\endgroup$ – Raphael Jul 7 '17 at 10:34
  • $\begingroup$ 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. $\endgroup$ – ryan Jul 7 '17 at 15:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.