DAG path enumeration

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

DAG path enumeration

Post by bugzpodder »

Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm? The best I've seen is to use matrix multiplication which is O(n^e(logn)) where e is the exponent for matrix multiplication. Is there a O(n^2 logn) solution? n is number of vertices. BFS seem to take O(n^3) times on this problem.

Note this is different from counting the number of paths between the two vertices, which can be done in O(E) time with topological sort.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Re: DAG path enumeration

Post by DP »

bugzpodder wrote:Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm?
I think DFS(depth first search) is the best, if you use adjacent list.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

DFS won't even solve the problem in polynomial time (BFS will, however).

Post Reply

Return to “Algorithms”