Q:

algorithm to find the total number of ways to reach the last layer from the initial one of a directed graph

I want an algorithm to find the total number of ways to reach the last layer from the initial one of a directed graph whose last and first layers contain only one node .Please suggest which algorithm should i use . 

A:

If there is cycle on the path from the first node to the last one, the number of paths is infinitely large.
Otherwise, there are no cycles, so a part of the graph we are interested in is acyclic(there a can be a cycle somewhere in the graph, but if does not lie on the path between the first and last node, it does not matter). That's why can use dynamic programming to count the number of paths:

The base case: f(start node) = 1.
Transitions: f(node) = sum f(neighbor) for all neighbors of the node. We can compute this value correctly because there is no cycle.
The answer is f(last node).

We can either use topological sort explicitly or write a recursive function with memoization(in both cases, the time and space complexity is linear).

