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
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: