This question already has an answer here:
- Count all paths between two vertices 1 answer
Given a directed a-cyclic graph G (unweighted), give algorithm which count all the paths from node s to node t, and calculate the run time complexity.
so I thought about the naive way to do this : 1)hold a counter (counter=0 at beginning) and start from vertex 's', loop through all 's' neighbors. 2) if one of the neighbors is 't', we increase counter +1 and function will end. else if it is not 't' but has neighbors continue recursively with 's' neighbor , otherwise function will end without changing counter value.
my problem is that i'm very confuse about run-time of this function and about the efficiency (I suppose it is very uneffiecent). I thought about using memorization, so that I would hold an array of all the vertex, and each index will represent the sum of the paths between vertex 'i' to. 't' but also here i'm very confused with the implementation and run time.
it will be great if some could help me with figuring out the run time of my suggestion (and the memorization idea also), and if there are another ideas to implement it efficiency it will be great .