algorithm - Find the number of paths that run through an edge between two vertex -

i have algorithm determine, in dag, number of paths each vertex specific vertex t (which has out-degree equal 0). choose other specific vertex s 0 in-degree. have develop algorithm determine, each edge (u, v), number of paths run through (u, v) s t in o(|v|+|e|).

i have tried modify bfs (since dfs think impossible reach solution) if have edge more 1 paths, doesn't work. suggest me or give me hint how can focus work solution?

by way, problem related topological sort.

thanks in advance! :)

you have answer previous question find number of paths vertices target node t.

so, in specific, using algorithm, have #paths v t.
using algorithm, can find paths s u.

the total number of paths s t uses (u,v) #paths(s,u) * #paths(v,t)

---

explanation:

number of paths s u given correctness of algorithm. have 1 choice go forward v, number of paths s v same number. now, can continue v t using each of #paths(v,t), giving total of #paths(s,u)*#paths(v,t)

complexity:

the algorithm requries find twice number of paths node node b, each o(v+e), complexity of algorithm o(v+e)

---

attachment: algorithm find #paths vertices target node t:

topological sort vertices, let ordered vertices v1,v2,...,vn create new array of size t, let arr init: arr[t] = 1 t-1 1 (descending, inclusive):     arr[i] = 0       each edge (v_i,v_j) such < j <= t:          arr[i] += arr[j] 

proof , analysis in original question (linked).