Counting Simple Paths in a DAG

Design an algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph on the right contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. Your algorithm should run in time O(V+E). (Your algorithm needs only to count the simple paths, not list them.)

Hints: Solve the more general case of number of paths to all vertices. Use topological sort to solve smaller problems before larger ones. Be sure to consider the boundary cases where s = t and where there are no simple paths between s and t.

(a) Write the pseudocode

(b) Explain why it works.

(c) Analyze its asymptotic run time.