2
$\begingroup$

The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?

$\endgroup$

2 Answers 2

2
$\begingroup$

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i < j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i < j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.

$\endgroup$
4
  • $\begingroup$ I'm not sure I understand your explanation. Lets say there are 3 neighbor vertices of vertex 0, then there should be 3 recursive call for subgraphs of size n-1. From your explanation, I think you only account for 1. $\endgroup$
    – Henry Wise
    Jan 16, 2020 at 3:56
  • $\begingroup$ Edited, hoping to have been more clear. $\endgroup$
    – Guanaco96
    Jan 17, 2020 at 1:12
  • $\begingroup$ I have read your proof over and over again and still not be able to jump from "calling the sam efunction on smaller instances of the same problem" to "satisfying the equation above". Can you clarify how you reach that equation? Also, I am unclear what topo sort has to do with anything here $\endgroup$
    – Henry Wise
    Jan 18, 2020 at 2:53
  • $\begingroup$ The main idea is that from the edge labelled as $\operatorname{TS}[i]$ you can reach only $n - i $ other vertices, then when you recursively call the function on a vertex you are facing a lower-sized instance of the same problem, since the function basically ignore nodes that cannot be reached. $\endgroup$
    – Guanaco96
    Jan 19, 2020 at 17:36
0
$\begingroup$

For directed graph :-

Suppose there are 7 vertices {0,1,2,3,4,5,6} and consider the worst case where every vertex is connected to every other vertex =>

No of edges required to reach from x to y vertices is as follows :

(6->6) 6 to 6 =0

(5->6) 5 to 6 =1

(4->6) 4 to 6 = (4 to 5 -> 6) + (4 to 6->6) = (1+( 5 -> 6)) + (1+0) =(1 + 1) + 1= 3

(3->6) 3 to 6 =(3 to 4 -> 6) + (3 to 5 -> 6 ) + (3 to 6->6) = (1+3) + (1+1) + (1+0)=7

(2->6) 2 to 6= 4+7+3+1=15

(1->6) 1 to 6= 5+15+7+3+1=31

(0->6) 0 to 6 = 6+5+15+7+3+1=63

So the time complexity to cover all the path to reach from 0 to 6= summation of (1+3+7+15+.....+T(n-1)+T(n))+(Total no of vertices -1) = (2^(n+1)-2-n)+(V-1)

value of n=V-1.

So final time complexity = O(2^V)

For undirected graph :-

Every edge will be traversed twice = 2*((2^(n+1)-2-n)+(V-1))=O(2^(V+1))

$\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.