Suppose there is a graph of which edges have integer weights. I want to get the number of paths of length n (natural number) from one particular vertex to another. Would there be a proper way to manipulate adjecency matrix or incidence matrix or exponential of incidence matrix or any other matrices to get this result?
Only a slightest hint will also be a big help.
Thanks in advance!
One approach would be to construct a directed graph in which each edge of length $k$ in the original is replaced by two directed paths, one in each direction (each with $k$ edges and $k-1$ completely new vertices).
The problem with this approach is that the resulting directed graph may be very large, especially if some of the weights are large.
On the other hand, the adjacency matrix of this graph will be very sparse, and you may be able to take advantage of some sort of block structure inside it.