算法导论22.4-2

• 问题描述
  请给出一个线性时间的算法，算法的输入为一个有向无环图$G=(V,E)$以及两个结点s和t，算法的输出是从结点s到结点t之前的简单路径的数量。
• 问题解答
  由于除了s与t相等的情况外，每一条从u到v的路径必定经过u的邻接结点，所以$\sum P_{u->v}$就是u的每个邻接结点到v的路径数的和。可以用如下伪代码表示：
  int SIMPLE-PATH-NUM(u,v)

if u==v
    return 1
else sum=0
     for each w in Adj[u]
         sum=sum+SIMPLE-PATH-NUM(w,v)
     return