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]:
  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?

  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 4 at 20:10
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 4 at 21:39

Your Answer

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

Browse other questions tagged or ask your own question.