The number of paths in the graph

Question

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

Best wishes

EDIT . A count is not a tree.

Answer 1

Let A be the adjacency matrix of the 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 is equal to the number of different paths of length n from vertex i to vertex j .

Consequently:

• represents the graph as an adjacency matrix A
• multiply A it with you several times until you get bored
• at each step: calculate the sum of all matrix elements and add it to the result, starting from 0

It might be wise to first check if G contains a loop, because in this case it contains infinitely many paths. To detect loops, set all edge weights to -1 and use Bellman-Ford.

Answer 2

All the search queries that I see relate to the number of paths from the given node to another given node. But here is an algorithm that should find the total number of paths anywhere in the graph for any acyclic digraph. (If there are loops, there are an infinite number of paths unless you indicate that certain duplicate paths are excluded.)

Designate each node with the number of paths that end with node:

 While not all nodes are labeled: Choose an unlabeled node with no unlabeled ancestors. (An implementation might here choose any node, and recursively process any unlabeled ancestors of that node first.) Label the node with one plus the sum of the labels on all ancestors. (If a node has no ancestors, its label is simply 1.) 

Now just add tags on all nodes.

If you do not want to count paths of length zero, subtract the number of nodes.

Answer 3

You can use the depth search . However, you do not stop the search when you find the path from the beginning to the destination, as the depth search usually does. Instead, you simply add paths to the score and return from this node, as if it were a dead end. This is probably not the fastest way, but it should work.

You can also use the width search, but then you need to develop a way to transmit information about tracing the path forward (or backward) through the tree when searching for it. If you could do this, it would probably be much faster.

Answer 4

Assuming the graph is acyclic (DAG), you can do topological sorting of vertices rather than dynamic programming to calculate the number of different paths. If you want to print all the paths, there is little point in discussing a large O, since the number of paths can be exponential in the number of vertices.

Pseudo Code:

 paths := 0 dp[i] := 0, for all 0 <= i < n compute topological sorting and store on ts for i from n - 1 to 0 for all edges (ts[i], v) // outbound edges from ts[i] dp[ts[i]] := 1 + dp[ts[i]] + dp[v] paths := paths + dp[ts[i]] print paths 

Edit: Error in code

Answer 5

I do not believe that there is anything faster than moving a graph, starting from the root.

In pseudo code -

 visit(node) { node.visited = true; for(int i = 0; i < node.paths.length; ++i) { ++pathCount; if (!node.paths[i].visited) visit(node.paths[i]); } } 

Answer 6

If it is really a tree, the number of paths is equal to the number of nodes-1, if you count the paths to the internal nodes. If you count only the paths to the leaves, the number of paths is equal to the number of leaves. Therefore, the fact that we are talking about trees simplifies matters only for counting nodes or leaves. A simple BFS or DFS algorithm will suffice.

Answer 7

admat gives a length of 1 path between vertices;

admat^2 gives the length of 2 paths between the vertices;

admat^3 gives a length of 3 paths between vertices;

Pokat template yet?

Answer 8

If the graph is not a tree, there will be endless paths - skip the loop at any time.