Home
> Uncategorized > Give an efficient algorithm to count total number of paths in a directed acyclic graph.

## Give an efficient algorithm to count total number of paths in a directed acyclic graph.

Prob :

Give an efficient algorithm to count total number of paths in a directed acyclic graph.

I don’t know whether the solution is correct. But here is my idea…

Solution:

1. Run Topological sorting on the graph and produce list of vertices L ( v1,v2… vn) in order as output.

2. For each vertices Vi in L

Run BFS with Vi as source

cumulatively sum-up paths of of all height ( height 1 , height 2 and so on ) .

Path += all paths from Vi as source vertex.

Advertisements

Categories: Uncategorized

Comments (0)
Trackbacks (0)
Leave a comment
Trackback