# Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B

If i apply dfs and increase counter for every node i visit, it wont find all paths for example if it finds A,A->B,A->B->C then after backtrack it wont traverse A->C and further A->C->B because C and B are marked as visited.

So i modified the dfs where i unmarked the visited node when algorithm backtracks to its parent.

Procedure dfs(arr,s,vis):  #s is source node
vis[s]=True              #mark as visited
count+=1                 #no of paths
for all i adjacent to s:
if not vis[i]:
dfs(arr,i,vis)
vis[s]=False             #mark visited as false again(modification)


After modification, algorithm gives correct result but the time complexity goes exponential.

Is there any optimized way to do it? Note that i am developing a game and in my specific scenario

• In-degree/Out-degree of any node is at most 4
• In-degree/Out-degree of source node is at most 2

Any idea?

• There is no efficient way to count the number of simple paths between two nodes in a directed graph in general. I would believe the same holds for the specific scenarios in the question. Mar 4, 2019 at 20:10
• Do you mean simple paths, or arbitrary paths? Is a path allowed to visit a vertex or edge more than once? Please edit the question to clarify what you mean by "path". You might also tell us the typical size of the graph (i.e., number of nodes), to give us a sense for how large a problem you need to deal with.
– D.W.
Mar 4, 2019 at 21:39