Give a linear-time 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 of Figure 22.8 contains exactly four simple paths from vertex p to vertex ?: po?, pory?, posry?, and psry?. (Your algorithm needs only to count the simple paths, not list them.)

Figure 22.8 A dag for topological sorting.

Transcribed Image Text:

m u