I was redirected from stackoverflow to ask here.   

I want to count a number of all paths between two nodes in graph. The graph can contain cycles. I have read a lot of articles about this problem but for DAG.


[Stackoverflow: Number of paths between two nodes in a DAG](https://stackoverflow.com/q/5164719/5645978)


At the moment I have implemented an algorithm to **find all paths** between two nodes. I can simply count the number of all paths using this algorithm but since it's NP-hard problem, it has ugly time complexity. ~~I am pretty sure I can solve my problem in polynomial time (but do not have a proof for it)~~.   
  

I was thinking about something using adjacency matrix multiplication, i.e. $A^k\_{ij}$ is equal to number of paths of length k between nodes i and j, and diameter of graph but I'm getting incorrect result for this.   
E.g. for E = {(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 3), (2, 1), (2, 4), (3, 4), (3, 2), (3, 0), (3, 1), (4, 2), (4, 3)} and V = {0, 1, 2, 3, 4} (simple "house" graph) there are only 7 paths between 0 and 2, but using matrix multiplication and diameter I got only 3 paths. Maybe it's just about misinterpretation of diameter since today it's the first time I have heard of diameter of graph.  
  

Any help would be appreciated.



Number of paths between two nodes
This is still a hard problem (#P-complete), so it almost certainly can’t be done in polynomial time. See Valiant, L. G. (1979). The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8, 410-421.


As for the other part of your question, I wonder if you’ve fallen prey to some terminological confusion. It seems clear that what you’re interested in is counting all the *simple* paths – paths that visit each node at most once – between two nodes. Multiplying adjacency matrices gives you something different: it counts all the paths, including non-simple ones that may double back on themselves or go round a loop.


