3. The longest-path algorithm described in class can also be used to count the number of...

  

Transcribed Image Text:

3. The longest-path algorithm described in class can also be used to count the number of different paths from the starting vertex s to each other vertex in a directed acyclic graph. To do so, set npaths(s) = 1, and for each other vertex v (processed in the order given by a topological ordering) set npaths(v) =npaths(u). บ-รับ That is, we just replace the max in the longest path algorithm by a sum. Then after this computation, npaths(v) will equal the number of paths from s to v. Suppose that s is at position 0 in a topological ordering of the graph, and the remaining vertices are in positions 1, 2, ..., n-1. If v is the vertex at position i in this ordering, what is the largest value that npaths(v) could possibly have, as a function of i? (Hint: use induction.) 3. The longest-path algorithm described in class can also be used to count the number of different paths from the starting vertex s to each other vertex in a directed acyclic graph. To do so, set npaths(s) = 1, and for each other vertex v (processed in the order given by a topological ordering) set npaths(v) =npaths(u). บ-รับ That is, we just replace the max in the longest path algorithm by a sum. Then after this computation, npaths(v) will equal the number of paths from s to v. Suppose that s is at position 0 in a topological ordering of the graph, and the remaining vertices are in positions 1, 2, ..., n-1. If v is the vertex at position i in this ordering, what is the largest value that npaths(v) could possibly have, as a function of i? (Hint: use induction.)