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

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.