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

Question

I have an algorithm to determine, in a DAG, the number of paths from each vertex to a specific vertex t (which has out-degree equal to 0). Now I choose other specific vertex s with 0 in-degree. I have to develop another algorithm to determine, for each edge (u, v), the number of paths that run through (u, v) from s to t in O(|V|+|E|).

I have tried to modify the BFS (since with a DFS I think is impossible to reach the solution) but if I have an edge with more than one paths, it doesn't work. Could you suggest me or give me a hint about how can I focus my work to get the solution?

By the way, the problem is related to topological sort.

Thanks so much in advance! :)

Yes, the problem is related to topological sort. You can use any order a topological sort produces to calculate what you want. — G. Bach, Aug 08 '13 at 12:47

score 1 · Answer 1 · edited May 23 '17 at 12:11

You already have an answer from your previous question to find number of paths from all vertices to a target node t.

So, in specific, using this algorithm, you have #paths from v to t.
Using this algorithm, you can also find paths from s to u.

The total number of paths from s to t that uses (u,v) is exactly #paths(s,u) * #paths(v,t)

Explanation:

Number of paths from s to u is given from correctness of algorithm. You have exactly one choice to go forward to v, thus number of paths from s to v is also the same number. Now, you can continue from v to t using each of the #paths(v,t), giving you total of #paths(s,u)*#paths(v,t)

Complexity:

The algorithm requries to find twice number of paths from node a to node b, each is O(V+E), so the complexity of this algorithm is also O(V+E)

Attachment: algorithm to find #paths from all vertices to a target node t:

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

Proof and analysis in the original question (linked).

But I have to use the result of the previous algorithm to solve this one. It's like I already have, in the vertex data structure, the number of paths to t. — Stratford, Aug 08 '13 at 14:58

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

1 Answers1