number of paths between [i] and [j] on a directed unweighted cyclic graph? 
Given a directed unweighted cyclic graph G consisting of up to 30 nodes and 30 edges find number of paths between i,j for all i,j in G
If there are infinite number of paths detect it


In this example the matrix would be:
    A B C D
A  0 1 0 1
B  0 0 0 1
C  0 1 0 2
D  0 0 0 0
What's an algorithm that can find such matrix? (else DP)
 A: Conveniently enough, I've something in my thesis on this. Let $A$ be the adjacency matrix that you describe. I'll just completely transcribe what seems relevant here:

We say a path with origin $x_0$ and extremity $x_r$, which we denote $x_0,x_1,\ldots,x_r$ is without backtracking if $x_{i+1}\neq x_{i-1}$ for all $i\in\{1,\ldots,r-1\}$. We define a series of matrices $A_r$ where
$$
(A_r)_{xy}=\#\text{ of paths of length $r$ without backtracking with origin $x$ and extremity $y$}.
$$
Given that $A_0=\text{Id}$ and $A_1=A$, the following allows us to recursively define $A_r$.
(i) $A_2=A_1^2-k\cdot\text{Id}.$
(ii) For $r\geq 2$, $A_{r+1}=A_rA_1-(k-1)\,A_{r-1}$.
PROOF:
(i) Let $x,y\in V$. Then $(A_1^2)_{xy}$ is the number of all paths of length 2 between $x$ and $y$.  If $x\neq y$, we cannot have backtracking, thus $(A_1^2)_{xy}=(A_2)_{xy}$. If $x=y$, then the only way for a path of length 2 between $x$ and itself is along of the exactly $k$ edges connected to $x$, and is therefore found through backtracking. Thus we must subtract $k\cdot\text{Id}$ to eliminate these choices, and thus $A_2=A_1^2-k\cdot\text{Id}$ as required.
(ii) As above, let $x,y\in V$. Then $(A_rA_1)_{xy}$ is the number of paths of length $r+1$ between $x$ and $y$ without backtracking, except possibly at the last step.  Let $x=x_0,\ldots,x_{r-1},x_r,x_{r+1}=y$ be such a path.  If $x_{r-1}\neq y$, then there cannot be backtracking and so $(A_{r+1})_{xy}=(A_rA_1)_{xy}$. However if $x_{r-1}=y$, then we have backtracking at the last step.  There are $(k-1)(A_{r-1})_{xy}$ such paths and they must be deleted. This completes the proof.

This insight is courtesy of Lemma 1.4.1 in Elementary Number Theory, Group Theory, and Ramanujan Graphs by Davidoff, Sarnak, and Valette.  Hopefully this can give you some insight into your algorithm. I should warn that my situation called for directed graphs, which made the adjacency matrix symmetric.  I believe this is stated in enough generality that there aren't insurmountable difficulties in applying this in your case.
