Given n (no. of vertices) and edges in the undirected graph . For each pair of vertices(say 'u', 'v') find(no need to output these) the number of distinct paths connecting these vertices('u','v') and output the minimum of these.(2<=n<=1500) required O(n^2) solution.
1) Make the adjacency matrix and call it A.
2) find matrix B=A+A^2+A^3+...+A^n.(Proof
3) B contains the answer and find minimum of its entries.
But I am unable to do step 2 efficiently .