number of paths in graph

Question

how could the number of paths in a directed graph calculated? Are there any algorithms for this purpose?

Best wishes

EDIT: The graph is not a tree.

Answer 1

Let A be the adjacency matrix of a graph G. Then A^n (i.e. A multiplied n times with itself) has the following interesting property:

The entry at position (i,j) of A^n equals the number of different paths of length n from vertex i to vertex j.

Hence:

• represent the graph as an adjacency matrix A
• multiply A it with itself repeatedly until you get bored
• in each step: compute the sum of all matrix elements and add it to the result, starting at 0

It might be wise to first check whether G contains a cycle, because in this case it contains infinitely many paths. In order to detect cycles, set all edge weights to -1 and use Bellman-Ford.