# Number of paths between two nodes

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.

• if the graph can contain cycles, and a cycle is on the path between s and t, shouldn't it contain infinite many paths? Oct 29, 2020 at 3:34